Cod sursa(job #4835)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 8 ianuarie 2007 11:50:31
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <cmath>

const int NMAX = 151;

int N, M, R, C;
int A[NMAX][NMAX];
long long S[NMAX << 1][NMAX << 1];
int s, c;

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

	fscanf(fin, " %d %d %d %d", &N, &M, &R, &C);

	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 <= (N << 1); ++i)
		for (j = 1; j <= (M << 1); ++j)
			S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + 
			          A[i > N ? i - N : i][j > M ? j - M : j];
}

void brute() {
	int i, j, k, l, t;
	long long aux;

	s = 0; c = 1;

	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j)
			for (k = R - 1; k < N; ++k)
				for (l = C - 1; l < M; ++l) {
					aux = S[i + k][j + l] - S[i + k][j - 1] - S[i - 1][j + l] + S[i - 1][j - 1];
					t = (k + 1) * (l + 1);
					if ((long long) s * t < (long long) c * aux)
						s = aux, c = t;
				}
}

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

	rez = ( (long long) s * 1000 ) / c;

	fprintf(fout, "%lld.%.3lld\n", rez / 1000, rez % 1000);

	fclose(fout);
}

int main() {
	
	read();

	prepare();

	brute();

	write();

	return 0;
}