# Cod sursa(job #4837)

Utilizator Data 8 ianuarie 2007 11:55:55 Balans 100 cpp done Arhiva de probleme 1.66 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 151;
const int PMAX = 1000;

int N, M, R, C, N1, M1, mx, seek;
int A[NMAX][NMAX];
long long S[NMAX << 1][NMAX << 1];

FILE *fin = fopen("balans.in", "rt");
int i, j;

fscanf(fin, " %d %d %d %d", &N, &M, &R, &C);
N1 = N << 1; M1 = M << 1;

for (i = 1; i <= N; ++i)
for (j = 1; j <= M; ++j)
fscanf(fin, " %d", &A[i][j]);

fclose(fin);
}

void prepare() {
int i, j;

for (i = 1; i <= N1; ++i)
for (j = 1; j <= M1; ++j)
S[i][j] = S[i - 1][j] + A[i > N ? i - N : i][j > M ? j - M : j] * PMAX;

for (i = 1; i <= N; ++i)
for (j = 1; j <= M; ++j)
mx = max(mx, A[i][j] * PMAX);

}

void solve() {
int pas, sp;
int i, j, k, p;
int poz[NMAX << 1], beg, end;
long long DQ[NMAX << 1];
long long T[NMAX << 1];
bool ok;

T[0] = 0;

for (pas = 1; pas <= mx; pas <<= 1);

for (seek = 0; pas; pas >>= 1)
if ((sp = seek + pas) <= mx) {

ok = false;
for (i = 1; i <= N && ok == false; ++i)
for (j = R; j <= N && ok == false; ++j) {
k = i + j;

for (p = 1; p <= M1; ++p)
T[p] = T[p - 1] + S[k][p] - S[i][p] - (long long) sp * j;

beg = 0; end = -1;
for (p = C; p <= M1 && ok == false; ++p) {

while (beg <= end && poz[beg] + M < p) ++beg;

while (beg <= end && DQ[end] > T[p - C]) --end;

++end;
DQ[end] = T[p - C];
poz[end] = p - C;

if (T[p] >= DQ[beg]) ok = true;
}
}

if (ok) seek = sp;

}
}

void write() {
FILE *fout = fopen("balans.out", "wt");

fprintf(fout, "%d.%.3d\n", seek / PMAX, seek % PMAX);

fclose(fout);
}

int main() {