Pagini recente » Cod sursa (job #389556) | Cod sursa (job #2459442) | Cod sursa (job #2986290) | Cod sursa (job #479658) | Cod sursa (job #600978)
Cod sursa(job #600978)
#include <cstdio>
#define MAXN 305
typedef long long ll;
int A[MAXN][MAXN], D[MAXN];
int 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+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;
}