Cod sursa(job #480971)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 30 august 2010 12:05:50
Problema Balans Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <deque>
#define Nmax 155*2
#define CT 1000

using namespace std;

deque< int > Deq;
int a[Nmax][Nmax],b[Nmax][Nmax],Sc[Nmax][Nmax];
int Sum[Nmax];
int N,M,R,C;

inline int Maxim(int x,int y){ return x>y ? x:y; }
inline int Minim(int x,int y){ return x<y ? x:y; }

int bun(int X){
	int i,i2,j,mx,sum_ac;
	for(i=1;i<=2*N;++i)
		for(j=1;j<=2*M;++j){
			b[i][j] = a[i][j]-X;
			Sc[i][j]=Sc[i-1][j]+b[i][j];
		}
	
	for(i=1; i<=2*N-R+1; ++i)
		for(i2=i+R-1; i2<=Minim(2*N,i+N-1); ++i2){
			while( ! Deq.empty() )Deq.pop_back();
			
			for(j=1;j<=2*M;++j) Sum[j]=Sum[j-1] + Sc[i2][j]-Sc[i-1][j];
			Deq.push_back(1);
			mx = Sum[C];
			
			for(j=C+1; j<=2*M; ++j){
				while( !Deq.empty() && Deq.front()+M-1 < j ) 
					Deq.pop_front();
				
				sum_ac=Sum[j]-Sum[j-C];
				while( !Deq.empty() && Sum[j]-Sum[Deq.back()-1] < sum_ac )
					Deq.pop_back();
				Deq.push_back(j-C+1);
				
				mx=Maxim(mx,Sum[j]-Sum[Deq.front()-1]);
			}
			
			if( mx >= 0 ) 
				return 1;
		}
	return 0;
}

int main(){
	int i,j,Max=0,l,r,m,rez;
	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",&a[i][j]),a[i][j]*=CT;
			b[i][j]=b[i+N][j]=b[i][j+M]=b[i+N][j+M]=a[i][j];
			a[i+N][j]=a[i][j+M]=a[i+N][j+M]=a[i][j];
			
			Max=Maxim(a[i][j],Max);
		}
	
	for(l=0, r=Max; l<=r; ){
		m=l+(r-l)/2;
		if( bun(m) ){
			rez=m;
			l=m+1;
		}
		else r=m-1;
	}
	
	printf("%.3lf\n",(rez*1.0/CT));
	fclose(stdin); fclose(stdout);
	return 0;
}