Cod sursa(job #331534)

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

using namespace std;

#define maxn 550

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;
    printf("%d\n", val);
    for(l1=0; l1<no; l1++)
    {
        for(l2=l1+r; l2<=n; l2++)
        if(l2-l1<=no)
        {    
            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);
            //    printf("%d ", sum[j]);
            }
         //   printf("\n");
            coa[1]=0;
            le=1;
            ri=1;
            for(j=0; j<=m-c; j++)
            {
                while(sum[j]<=sum[coa[ri]] && ri>=le)
                {
                    --ri;
                }
                coa[++ri]=j;
                while(coa[le]<j+c-mo)
                {
                    le++;
                }
                if(sum[j+c]-sum[coa[le]]>=0)
                {
          //          printf("%d %d %d %d\n", l1, l2, coa[le], j+c);
                    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];
            printf("%d ", s[i][j]);
        }
        printf("\n");
    }
    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("%lld.%03lld\n", sol/1000, sol%1000);
    return 0;
}