Pagini recente » Cod sursa (job #1394915) | Cod sursa (job #436405) | Cod sursa (job #977723) | Cod sursa (job #2505691) | Cod sursa (job #601012)
Cod sursa(job #601012)
#include <cstdio>
#define MAXN 305
int A[MAXN][MAXN], D[MAXN];
long long S[MAXN][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; k<=M; k++){
if(l<=r && k-D[l]>oldM)
l++;
while(l<=r && sum[D[r]]<=sum[k-C])
r--;
D[++r]=k-C;
if(l<=r && sum[D[l]]>=sum[k])
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.", r/1000);
if(r%1000 < 10) printf("00");
else if(r%1000 < 100) printf("0");
printf("%d\n", r%1000);
return 0;
}