Pagini recente » Cod sursa (job #364055) | Cod sursa (job #2540614) | Monitorul de evaluare | Cod sursa (job #1285848) | Cod sursa (job #44)
Cod sursa(job #44)
#include <cstdio>
using namespace std;
const char iname[] = "balans.in";
const char oname[] = "balans.out";
const int MaxD = 301;
const int infinity = 1000000000;
#define MargSup 100000000
#define max(a,b) ((a) > (b) ? (a) : (b))
int N, M, R, C;
int A[MaxD][MaxD];
long long Sum[MaxD], X[MaxD][MaxD];
int deque[MaxD], head, tail;
int Ni, Mi;
void read_data(void)
{
freopen(iname, "r", stdin);
int i, j;
scanf("%d %d %d %d\n", &N, &M, &R, &C);
for (i = 1; i <= N; ++i)
for (j = 1; j <= M; ++j) {
scanf("%d ", A[i]+j);
A[i][j+M] = A[i+N][j] = A[i+N][j+M] = A[i][j] *= 1000;
}
Ni = N, Mi = M;
N = 2*Ni-1, M = 2*Mi-1;
}
void print(int m)
{
freopen(oname, "w", stdout);
printf("%d.", m / 1000);
m = m % 1000;
if (m < 100) printf("0");
if (m < 10) printf("0");
printf("%d", m);
}
int determina_balans(const int balans)
{
int i, j, k;
long long smax = -infinity;
for (i = 1; i <= N; ++i)
for (j = 1; j <= M; ++j)
X[i][j] = X[i-1][j] + (long long)(A[i][j] - balans);
for (k = 1; k <= Ni; ++k)
for (i = k+R-1; i <= N && i < k+Ni; ++i)
{
head = 0;
tail = 1;
deque[0] = 0;
for (j = 1; j <= M; ++j)
{
Sum[j] = Sum[j-1] + (X[i][j] - X[k-1][j]);
if (j >= C) {
while (head < tail && deque[head] < j-Mi)
++head;
if (smax < Sum[j] - Sum[deque[head]])
smax = Sum[j] - Sum[deque[head]];
while (head < tail && Sum[j-C+1] <= Sum[deque[tail-1]])
--tail;
deque[tail++] = j-C+1;
}
}
}
return (smax >= 0);
}
int main(void)
{
read_data();
int k, step;
for (step = 1; step <= MargSup; step <<= 1) ;
for (k = 0; step; step >>= 1)
if (k + step <= MargSup && determina_balans(k + step))
k += step;
print(k);
return 0;
}