Cod sursa(job #850414)

Utilizator dariusdariusMarian Darius dariusdarius Data 8 ianuarie 2013 15:09:34
Problema Balans Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h>
#include<string.h>
int n,m,r,c,a[305][305];
int d[305][305];
inline int min(int a,int b) {return a>b?b:a;}
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,j1,j2;
    touch(-x); memset(d,0,sizeof(d));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            d[i][j]=a[i][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
    for(i1=1;i1<=n;i1++)
        for(i2=i1+r-1;i2<=min(i1+n/2-1,n);i2++)
            for(j1=1;j1<=m;j1++)
                for(j2=j1+c-1;j2<=min(m,j1+m/2-1);j2++)
                    if(d[i2][j2]+d[i1-1][j1-1]-d[i1-1][j2]-d[i2][j1-1]>=0)
                    {
                        touch(x);
                        return true;
                    }
    touch(x); return false;
}
int main()
{
    freopen("balans.in","r",stdin);
    freopen("balans.out","w",stdout);
    int i,j,max=0;
    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]=10000*a[i][j];
            a[n+i][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
            if(a[i][j]>max) max=a[i][j];
        }
    n=2*n;m=2*m;
    int st,dr,med,last;
    st=0;dr=max;last=0;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if(good(med))
        {
            last=med;
            st=med+1;
        }
        else
            dr=med-1;
    }
    printf("%d.%03d",last/10000,last%10000/10);
    return 0;
}