Pagini recente » Cod sursa (job #1888669) | Cod sursa (job #2862038) | Cod sursa (job #2114248) | Cod sursa (job #1782399) | Cod sursa (job #493386)
Cod sursa(job #493386)
#include <stdio.h>
#define NMAX 305
#define ll long long
int n,m,p,q,A[NMAX][NMAX];
ll S[NMAX][NMAX],C[NMAX],D[NMAX],E[NMAX];
void read()
{
scanf("%d%d%d%d",&n,&m,&p,&q);
int i,j;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
scanf("%d",&A[i][j]);
for (j=m+1; j<2*m; j++)
A[i][j]=A[i][j-m];
}
for (i=n+1; i<2*n; i++)
for (j=1; j<2*m; j++)
A[i][j]=A[i-n][j];
n=2*n-1; m=2*m-1;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
A[i][j]*=10000;
S[i][j]=S[i-1][j]+A[i][j];
}
}
inline ll min(ll x,ll y)
{
return x<y ? x : y;
}
bool ok(int val)
{
int i,j,k;
for (i=1; i<=n-p+1; i++)
for (j=i+p-1; j<=n; j++)
{
for (k=1; k<=m; k++)
C[k]=(S[j][k]-S[i-1][k])-(ll)val*(j-i+1);
for (k=1; k<=m; k++)
{
E[k]=E[k-1]+C[k];
D[k]=min(D[k-1],E[k]);
if (k>=q)
if (E[k]-D[k-q]>0)
return 1;
}
}
return 0;
}
ll cbin()
{
ll i,step=(1<<30);
for (i=0; step; step>>=1)
if (ok(i+step))
i+=step;
return i;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
read();
ll ans=cbin();
printf("%lld.%lld\n",ans/10000,(ans%10000)/10);
return 0;
}