Pagini recente » Cod sursa (job #2377478) | Cod sursa (job #239497) | Cod sursa (job #722687) | Cod sursa (job #2735169) | Cod sursa (job #600970)
Cod sursa(job #600970)
#include <cstdio>
#define MAXN 305
typedef long long ll;
long long A[MAXN][MAXN], S[MAXN][MAXN], D[MAXN], sum[MAXN];
int N, M, R, C, oldN, oldM;
int check(long long 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*(ll)i*(ll)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;
long long 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("%lld", 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=1000000000;
while(l<=r){
mid=((r-l)>>1)+l;
if(check(mid))
l=mid+1;
else
r=mid-1;
}
printf("%lld.%.3lld\n", r/1000, r%1000);
return 0;
}