Cod sursa(job #600966)

Utilizator Smaug-Andrei C. Smaug- Data 4 iulie 2011 14:59:24
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>

#define MAXN 305

int A[MAXN][MAXN], S[MAXN][MAXN], D[MAXN], sum[MAXN];
int N, M, R, C, oldN, oldM;

int check(int X){

  int i, j, k, l, r;

  for(i=1; i<=N; i++)
    for(j=1; j<=M; j++)
      S[i][j]=A[i][j]-X*i*j;

  for(i=0; i<=N; i++)
    for(j=i+R; j<=N && j-i<=oldN; j++){
      for(k=1; k<=M; k++)
	sum[k]=S[i][k]-S[j][k];

      l=1; r=0;      
      for(k=C+1; k<=M; k++){
	if(l<=r && k-D[l]>oldM)
	  l++;
	while(l<=r && sum[D[r]]<=sum[k])
	  r--;
	
	D[++r]=k-C;

	if(l<=r && sum[D[l]]-sum[k] >= 0)
	  return 1;
      }
    }

  return 0;

}

int main(){

  freopen("balans.in", "r", stdin);
  freopen("balans.out", "w", stdout);

  int i, j;
  int l, r, mid;

  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]*=1000;
      A[i+N][j]=A[i][j+M]=A[i+N][j+M]=A[i][j];
    }

  oldN=N; oldM=M;
  N=N<<1; M=M<<1;

  for(i=1; i<=N; i++)
    for(j=1; j<=M; j++)
      A[i][j]=A[i][j]+A[i][j-1]+A[i-1][j]-A[i-1][j-1];

  l=0; r=100000000;

  while(l<=r){
    mid=((r-l)>>1)+l;
    if(check(mid))
      l=mid+1;
    else
      r=mid-1;
  }

  printf("%d.%.3d\n", r/1000, r%1000);

  return 0;

}