Cod sursa(job #331736)

Utilizator katakunaCazacu Alexandru katakuna Data 15 iulie 2009 09:13:26
Problema Balans Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>

#define Nmax 310

int n, m, r, c, N, i, j, p, u, mij, sol, MAX, M, l;
int a[Nmax][Nmax], d[Nmax], Min;
long long Sum, S[Nmax][Nmax], v[Nmax], INF;

int cont ( int X ){
	
	int p, u;
	long long Sum = - INF;

	for (i = 1; i <= N; i++){
		
		j = i + r - 1; if( j > N) break;
		for(; j <= N; j++){
			
			for(l = 1; l <= M; l++){
				v[l] = S[j][l] - S[i-1][l] - (long long)X * (long long)(j - i + 1);
				v[l]+= v[l-1];
			}
			
			p = u = 1; Min = 0; 
			for(l = 1; l + c <= M && l <= M; l++){
				if(Min > v[l]) Min = v[l];
				if(Sum < v[l + c ] - Min  ) Sum = v[l + c ] - Min;
			}
			
		}
	}
	
	
	if( Sum >= 0 ) return 1;
	return 0;
	
}

int main (){

	FILE *f = fopen("balans.in", "r");
	FILE *g = fopen("balans.out", "w");
	
	fscanf(f,"%d %d %d %d", &n, &m, &r, &c);
	for (i = 1; i <= n; i++)
		for(j = 1; j <= m; j++){
			fscanf(f,"%d", &a[i][j]); a[i][j]*= 1000;
			if(MAX < a[i][j]) MAX = a[i][j];
		}
	
	N = n << 1; M = m << 1;
	for (i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			a[i][j+m] = a[i][j];
	
	for (i = 1; i <= n; i++)
		for(j = 1; j <= M; j++)
			a[i+n][j] = a[i][j];
	

	for(i = 1; i <= N; i++)
		for(j = 1; j <= M; j++)
			S[i][j] = S[i-1][j] + (long long)a[i][j];
	
	p = 0; u = MAX; INF = 1 << 30; INF*= 2000;
	while(p <= u){
		mij = (p + u) >> 1;
		if( cont(mij) ){
			sol = mij;
			p = mij + 1;
		}
		
		else
			u = mij - 1;
	}
	
	fprintf(g,"%.3lf", (double)((double)sol / (double)1000) );
	
	fclose(f);
	fclose(g);
	
	return 0;

}