Cod sursa(job #850483)

Utilizator dariusdariusMarian Darius dariusdarius Data 8 ianuarie 2013 16:10:05
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<string.h>
int n,m,r,c,a[305][305];
long long d[305][305],v[305];int deque[305];
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,p,u,N,M;N=n/2;M=m/2;
    touch(-x);
    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<=n;i2++)
        {
            if(i2-i1+1>N) break;
            for(j=1;j<=m;j++)
                v[j]=v[j-1] + (d[i2][j]-d[i1-1][j]);
            p=1;u=0;memset(deque,0,sizeof(deque));
            for(j=c+1;j<=m;j++)
            {
                deque[++u]=j-c;
                while(v[deque[u]] < v[deque[u-1]] && u>p)
                {
                    deque[u-1]=deque[u];deque[u]=0;
                    u--;
                }
                while(deque[p]<j-M+1 && p<u) p++;
                if(v[j]>=v[deque[p]]) {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]=1000*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;
    }
    double ans;
    ans=(double)last/1000;
    printf("%.3lf\n",ans-0.000499);
    return 0;
}