Pagini recente » Cod sursa (job #3205498) | Cod sursa (job #2621541) | Cod sursa (job #1354233) | Cod sursa (job #2160017) | Cod sursa (job #4742)
Cod sursa(job #4742)
#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];
int S[NMAX << 1][NMAX << 1];
int CS[NMAX << 1][NMAX << 1];
long long T[NMAX << 1];
void read() {
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];
int best;
for (pas = 1; pas <= mx; pas <<= 1);
for (seek = 0; pas; pas >>= 1)
if ((sp = seek + pas) <= mx) {
best = -1;
for (i = 1; i <= N; ++i)
for (j = R; j <= N; ++j) {
k = i + j;
for (p = 1; p <= M1; ++p)
T[p] = T[p - 1] + S[k][p] - S[i][p] - sp * j;
beg = 0; end = -1;
for (p = C; p <= M1; ++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;
best >?= T[p] - DQ[beg];
}
}
if (best >= 0) seek = sp;
}
}
void write() {
FILE *fout = fopen("balans.out", "wt");
fprintf(fout, "%d.%3d\n", seek / 1000, seek % 1000);
fclose(fout);
}
int main() {
read();
prepare();
solve();
write();
return 0;
}