Cod sursa(job #1621523)

Utilizator cnitv1CNITV Paul Radu Mihai cnitv1 Data 29 februarie 2016 19:43:08
Problema Balans Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iomanip>

FILE* in=fopen("balans.in","r");
//FILE* out=fopen("balans.out","w");

std::ofstream out("balans.out");

using namespace std;

const int Q=160;

int n,m,r,c;

int v[2*Q][2*Q];

int nrlin;

long long act[2*Q];

bool mergee(long long r)
{
    r*=nrlin;
    long long meu=0;

    for(int i=1; i<=c; i++)
    {
        meu+=act[i]-r;
    }
    if(meu>=0)
        return 1;

    int st=1;

    long long befor=0;

    for(int i=c+1; i<=2*m; i++)
    {
        while(i-st+1>m)
        {
            befor-=act[st]-r;
            st++;
        }

        if(befor+act[i-c]-r > act[i-c])
            befor+=act[i-c]-r;
        else
        {
            befor=act[i-c]-r;
            st=i-c;
        }
        if(befor<0)
        {
            befor=0;
            st=i-c+1;
        }

        meu-=act[i-c]-r;
        meu+=act[i]-r;
        if(meu+befor>=0)
            return 1;
    }
    return 0;
}

long long ask()
{
    long long p=1<<30;
    long long rez=0;

    while(p)
    {
        if(mergee(rez+p))
            rez+=p;
        p/=2;
    }
    return rez;
}

int main()
{
    fscanf(in,"%d%d%d%d",&n,&m,&r,&c);

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            fscanf(in,"%d",&v[i][j]);
            v[i][j]*=1000;
            v[i+n][j]=v[i][j];
            v[i][j+m]=v[i][j];
            v[i+n][j+m]=v[i][j];
        }
    }

    long long best=0;

    long long far;

    for(nrlin=r; nrlin<=n; nrlin++)
    {
        memset(act,0,sizeof act);
        for(int i=1; i<=2*m; i++)
        {
            for(int j=1; j<nrlin; j++)
            {
                act[i]+=v[j][i];
            }
        }

        for(int i=nrlin; i<=2*n-nrlin+1; i++)
        {
            for(int j=1; j<=2*m; j++)
            {
                act[j]-=v[i-nrlin][j];
                act[j]+=v[i][j];
            }

            far=ask();
            if(far>best)
                best=far;
        }
    }

    out << fixed << setprecision(3) << best / 1000 << '.' << setw(3) << setfill('0') << best % 1000 << '\n';

    return 0;
}