Pagini recente » Cod sursa (job #468905) | Cod sursa (job #700972) | Cod sursa (job #701119) | Cod sursa (job #2641110) | Cod sursa (job #850365)
Cod sursa(job #850365)
#include<stdio.h>
#include<string.h>
int n,m,r,c,a[305][305];
int d[305][305];
int v[305];
inline int min(int a,int b) {return a>b?b:a;}
void afis(int x)
{
printf("%d.",x/1000);
if(x%1000>99) printf("%d\n",x%1000);
else
if(x%1000>9) printf("0%d\n",x%1000);
else printf("00%d\n",x%1000);
}
inline void touch(int x)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]+=x;
}
bool good(int x)
{
int i1,i2,i,j;bool ans=false;
touch(-x);
memset(d,0,sizeof(d));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
d[i][j]=d[i-1][j]+a[i][j];
for(i1=1;i1<=n;i1++)
for(i2=i1+r-1;i2<=min(n,i1+n/2-1);i2++)
{
for(j=1;j<=m;j++)
v[j]=d[i2][j]-d[i1-1][j];
for(j=2;j<=m;j++)
v[j]+=v[j-1];
int minim=0;
for(j=1;j<=m;j++)
{
if(v[j]-minim>=0) {touch(x);return true;}
if(v[j]<minim) minim=v[j];
}
}
touch(x);
return false;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
int i,j;
scanf("%d%d%d%d",&n,&m,&r,&c);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);a[i][j]=1000*a[i][j];
a[n+i][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
}
n=2*n;m=2*m;
int st,dr,med,last;
st=0;dr=100000000;last=0;
while(st<=dr)
{
med=(st+dr)/2;
if(good(med)) last=med,st=med+1;
else dr=med-1;
}
afis(last);
return 0;
}