Cod sursa(job #1413963)

Utilizator stefanzzzStefan Popa stefanzzz Data 2 aprilie 2015 11:22:07
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <deque>
#define MAXN 160
#define MAXVAL 100005
using namespace std;

int n, m, r, c, a[2 * MAXN][2 * MAXN], i1, i2, nr, Sp[2 * MAXN][2 * MAXN], S;
double sol;

int main(){
	freopen("balans.in", "r", stdin);
	freopen("balans.out", "w", stdout);

	int i, j, difi, difj;
	
	scanf("%d %d %d %d", &n, &m, &r, &c);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++){
			scanf("%d", &a[i][j]);
			a[i + n][j] = a[i + n][j + m] = a[i][j + m] = a[i][j];
		}
		
	for(i = 1; i <= 2 * n; i++)
		for(j = 1; j <= 2 * m; j++)
			Sp[i][j] = Sp[i - 1][j] + Sp[i][j - 1] - Sp[i - 1][j - 1] + a[i][j];
	
	for(difi = r; difi <= n; difi++)
		for(difj = c; difj <= m; difj++){
			nr = difi * difj;
			for(i = n + 1; i <= 2 * n; i++)
				for(j = m + 1; j <= 2 * m; j++){
					S = Sp[i][j] + Sp[i - difi][j - difj] - Sp[i][j - difj] - Sp[i - difi][j];
					if(S > sol * nr) sol = (double)S / nr;
				}
		}

	printf("%.3lf\n", (int)(sol * 1000) / 1000.0);
	return 0;
}