Cod sursa(job #331514)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 14 iulie 2009 12:04:48
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <stdio.h>

using namespace std;

#define maxn 350

long long n, m, i, j, k, r, c, left, right, med, sol, no, mo;
long long v[maxn][maxn], s[maxn][maxn];
long long coa[maxn], sum[maxn];

long verif(long val)
{
    long l1, l2, rez, le, ri;
    rez=-2000000000*1000;
    for(l1=0; l1<no; l1++)
    {
        for(l2=l1+r; l2<=n; l2++)
        {
            for(j=0; j<=m; j++)
            {
                sum[j]=0;
            }
            for(j=1; j<=m; j++)
            {
                sum[j]=sum[j-1]+s[l2][j]-s[l1][j]-val*(l2-l1);

            }
            coa[1]=0;
            le=1;
            ri=1;
            for(j=0; j<=m-c; j++)
            {
                while(sum[j]<=sum[coa[ri]] && ri>=le)
                {
                    --ri;
                }
                while(coa[le]<j+c-mo)
                {
                    le++;
                }
                coa[++ri]=j;
                if(rez<sum[j+c]-sum[coa[le]])
                {
                    rez=sum[j+c]-sum[coa[le]];
                }
            }           
        }
    }
    if(rez>=0) return 1;
    return 0;
}

int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &r, &c);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            scanf("%d", &v[i][j]);
            v[i][j]*=1000;
            v[i+n][j]=v[i][j];
            v[i+n][j+m]=v[i][j];
            v[i][j+m]=v[i][j];
        }
    }
    no=n;
    mo=m;
    n*=2;
    m*=2;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            s[i][j]=s[i-1][j]+v[i][j];
        }
    }
    left=0;
    right=100000000;
/*    while(left<=right)
    {
        med=(left+right)/2;
        if(verif(med))
        {
            left=med+1;
            if(med>sol) sol=med;
        }
        else
        {
            right=med-1;
        }
    }*/
    printf("%d.%03d\n", sol/1000, sol%1000);
}