Pagini recente » Cod sursa (job #3267147) | Cod sursa (job #103855) | Cod sursa (job #785784) | Cod sursa (job #2065088) | Cod sursa (job #394470)
Cod sursa(job #394470)
#include <algorithm>
#include <stdio.h>
#define ll long long
#define MAX 310
using namespace std;
int n, m, r, c, pos, lung, sol;
ll suma[MAX], s[MAX];
int deqMin[MAX];
int a[MAX][MAX];
inline ll calc(int x)
{
for (int i = 1; i <= 2 * m; i++)
s[i] = s[i - 1] + suma[i] - x * lung;
int deqSt = 1, deqSf = 0;
ll maxGs = -1;
for (int i = 1; i < 61; i++)
maxGs *= (ll) 2;
for (int i = 1; i <= 2 * m; i++)
if (i >= c)
{
deqMin[++deqSf] = i - c;
for (; deqSf > 1 && s[deqMin[deqSf]] < s[deqMin[deqSf - 1]]; deqSf--)
swap(deqMin[deqSf], deqMin[deqSf - 1]);
if (deqMin[deqSt] <= i - m)
deqSt++;
maxGs = max(maxGs, s[i] - s[deqMin[deqSt]]);
}
return maxGs;
}
inline void cautaBin(int st, int dr)
{
if (st > dr)
return;
int med = (st + dr) / 2;
if (calc(med) >= 0)
{
pos = med;
cautaBin(med + 1, dr);
}
else cautaBin(st, med - 1);
}
int main()
{
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &r, &c);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
a[i][j] *= 1000;
a[n + i][j] = a[i][m + j] = a[n + i][m + j] = a[i][j];
}
for (lung = r; lung <= n; lung++)
{
memset(suma, 0, sizeof(suma));
for (int i = 1; i < lung; i++)
for (int j = 1; j <= 2 * m; j++)
suma[j] += (ll) a[i][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 2 * m; j++)
suma[j] += (ll) a[i + lung][j] - a[i - 1][j];
cautaBin(0, 100000000);
sol = max(sol, pos);
}
}
printf("%.3lf\n", (double) sol / 1000);
fclose(stdin);
fclose(stdout);
return 0;
}