Cod sursa(job #850481)

Utilizator dariusdariusMarian Darius dariusdarius Data 8 ianuarie 2013 16:05:57
Problema Balans Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<stdio.h>
#include<string.h>
long long n,m,r,c,a[305][305];
long long d[305][305];
long long v[305],deque[305];
inline long long min(long long a,long long b) {return a>b?b:a;}
inline void touch(long long x) {long long i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]+=x;}
bool good(long long x)
{
    long long i1,i2,i,j,p,u;
    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/2;i1++)
        for(i2=i1+r-1;i2<=n;i2++)
        {
            if(i2-i1+1>n/2) 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/2+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);
    long long i,j,max=0;
    scanf("%lld%lld%lld%lld",&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;
    long long 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;
}