Cod sursa(job #600976)

Utilizator Smaug-Andrei C. Smaug- Data 4 iulie 2011 15:36:00
Problema Balans Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

#define MAXN 305

typedef long long ll;

int A[MAXN][MAXN];
long long 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;

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

  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);
  l=1<<30; r=0;
  for(i=1; i<=N; i++)
    for(j=1; j<=M; j++){
      scanf("%d", A[i]+j);
      A[i][j]*=1000;
      r=(r<A[i][j])? A[i][j]: r;
      l=(l>A[i][j])? A[i][j]: l;
      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;

  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;

}