Cod sursa(job #480992)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 30 august 2010 12:39:58
Problema Balans Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <deque>
#define Nmax 155*2
#define CT 1000
#define LL long long

using namespace std;

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

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

int bun(LL X){
	int i,i2,j,q; LL mx,sum_ac;
	for(i=1;i<=2*N;++i)
		for(j=1;j<=2*M;++j)
			Sc[i][j]=Sc[i-1][j]+(LL)(a[i][j]-X);
	
	for(i=1; i<=2*N-R+1; ++i)
		for(i2=i+R-1, q=Minim(2*N,i+N-1); i2<=q; ++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;
			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;
}