Cod sursa(job #331672)

Utilizator katakunaCazacu Alexandru katakuna Data 14 iulie 2009 22:31:34
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 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], v[Nmax], d[Nmax], S[Nmax][Nmax];

int cont ( int X ){
	
	int Sum = - 1<<30, p, u;
	
	for (i = 1; i <= N; i++){
		for(j = i + r - 1; j <= N; j++){
			
			for(l = 1; l <= M; l++)
				v[l] = S[j][l]*1000 - S[i-1][l]*1000 - X * (j - i + 1);
			
			p = u = 1; d[1] = 1;
			for(l = 1; l <= M; l++){
				
				while( p <= u && l - d[p] >= c  ) p++;
				while( p <= u && v[ d[u] ] <= v[l] ) u--;
				d[++u] = i;
				
				if(l >= c && Sum < v[ d[p] ]) Sum = v[ d[p] ];
			}
			
		}
	}
	
	
	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]);
			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] + a[i][j];
	
	p = 0; u = MAX * 1000;
	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;

}