Cod sursa(job #2362762)

Utilizator Andrei_RAndrei Roceanu Andrei_R Data 3 martie 2019 11:49:30
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb

#include <stdio.h>
#define Nmax 155*2
#define CT 1000
#define LL long long
#define INF 2147000000

using namespace std;

int Deq[Nmax];
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,p,u; LL mx,sum_ac;

	for(i=1; i<=N; ++i)
		for(i2=i+R-1; i2<=i+N-1; ++i2){

			for(j=1;j<=2*M;++j) Sum[j]=Sum[j-1] + Sc[i2][j]-Sc[i-1][j] -X*(i2-i+1);

			p=1; u=0; mx=Sum[C];
			Deq[1]=1;
			for(j=C+1; j<=2*M; ++j){
				while( p<=u && Deq[p]+M-1 < j )
					p++;

				sum_ac=Sum[j]-Sum[j-C];
				while( u>=p && Sum[j]-Sum[Deq[u]-1] <= sum_ac )
					u--;
				Deq[++u]=j-C+1;

				mx=Maxim(mx,Sum[j]-Sum[Deq[p]-1]);
				if( Deq[p]>M ) break;
			}
			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(i=1;i<=2*N;++i)
		for(j=1;j<=2*M;++j)
			Sc[i][j]=Sc[i-1][j]+(LL)(a[i][j]);

	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;
}