Cod sursa(job #850365)

Utilizator dariusdariusMarian Darius dariusdarius Data 8 ianuarie 2013 13:25:03
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#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;
}