Cod sursa(job #4837)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 8 ianuarie 2007 11:55:55
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 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];

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];
	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() {
	
	read();

	prepare();

	solve();

	write();

	return 0;
}