Cod sursa(job #1413937)

Utilizator stefanzzzStefan Popa stefanzzz Data 2 aprilie 2015 11:08:33
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <deque>
#define MAXN 160
#define MAXVAL 100005
#define INF 2000000000000000000
using namespace std;

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

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][j] *= 1000;
		}
	
	for(i = n + 1; i <= 2 * n; i++)
		for(j = 1; j <= m; j++)
			a[i][j] = a[i - n][j];
	
	for(i = 1; i <= n; i++)
		for(j = m + 1; j <= 2 * m; j++)
			a[i][j] = a[i][j - m];
	
	for(i = n + 1; i <= 2 * n; i++)
		for(j = m + 1; j <= 2 * m; j++)
			a[i][j] = a[i - n][j - m];
	
	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 = 1; i <= n; i++)
				for(j = 1; j <= m; j++){
					S = Sp[i + difi - 1][j + difj - 1] + Sp[i - 1][j - 1] - Sp[i + difi - 1][j - 1] - Sp[i - 1][j + difj - 1];
					if(S / nr > sol) sol = S / nr;
				}
		}

	printf("%d.%03d\n", sol / 1000, sol % 1000);
	return 0;
}