Cod sursa(job #4742)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 6 ianuarie 2007 20:47:12
Problema Balans Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 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];
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;
}