Cod sursa(job #934411)

Utilizator veleanduAlex Velea veleandu Data 30 martie 2013 16:43:04
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <iostream>
using namespace std;

const int max_n=305;
const double EPS=0.00000001;

int El[max_n][max_n];
int n,m,R,C;
int i,j;

bool bs( double rez ){
 	double SP[max_n][max_n];
	int Deq[max_n];
	int i,j,l1,l2,c,st,dr;
 	for( i=0; i<max_n; ++i )
		SP[i][0]=SP[0][i]=0.0;
	for( i=1; i<=n; ++i )
		for( j=1; j<=m; ++j ){
			SP[i][j] = SP[i][j-1] + SP[i-1][j] - SP[i-1][j-1] + El[i][j] - rez;
		}
	for( l1=1; l1<=n; ++l1 )
		for( l2=l1+R-1; l2<=n; ++l2 ){
			// calculam de la 0
			dr=0;
			st=1;
			for( c=C; c<=m; ++c ){
				// introducem coloana c-C/
				while( dr && ( SP[l2][c-C] - SP[l1-1][c-C] - SP[l2][Deq[dr]] + SP[l1-1][Deq[dr]] < EPS ) ) 
					dr--;
				Deq[++dr]=c-C;
				if( Deq[st] == c-m/2 )
					++st;
				if( SP[l2][c] - SP[l1-1][c] - SP[l2][ Deq[st] ] + SP[l1-1][ Deq[st] ] > 0 ){
					return true;
				}
			}
		}
	return false;
}

int main(){
	freopen("balans.in","r",stdin);
	freopen("balans.out","w",stdout);
	scanf("%d %d %d %d", &n, &m, &R, &C );
	for( i=1; i<=n; ++i )
		for( j=1; j<=m; ++j ){
			scanf("%d", &El[i][j] );
			El[i+n][j]=El[i][j];
			El[i][j+m]=El[i][j];
			El[i+n][j+m]=El[i][j];
		}
	n*=2;
	m*=2;
	double rez=0.0, p=(1<<20)*1.0;
	int target=35;
	for( ; target; target--, p/=2.0 )
		if( bs( rez+p ) )
			rez+=p;
	printf("%.3lf", rez);
	return 0;
}