Cod sursa(job #788950)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 16 septembrie 2012 11:51:02
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <iomanip>
#define NM 310
#define Z 1000

using namespace std;

ifstream f("balans.in");
ofstream g("balans.out");

int N,M,i,j,R,C,MX,ZN;
int A[NM][NM];
long long SUM[NM][NM];
int ANS=0;
long long V[NM];
long long Min[NM];
int l1,l2;

void Read ()
{
    f >> N >> M >> R >> C;
    ZN=N;
    V[0]=Min[0]=0;
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
        {
            f >> A[i][j];
            A[i][j]*=Z;
            MX=max(MX,A[i][j]);
            A[i+N][j]=A[i][j];
            A[i][j+M]=A[i][j];
            A[i+N][j+M]=A[i][j];
        }
    N<<=1;
    M<<=1;
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            SUM[i][j]=SUM[i-1][j]+1LL*A[i][j];

    f.close();
}

bool Check (int X)
{
    for (l1=1; l1<=ZN; l1++)
        for (l2=l1+R-1; l2<=l1+ZN-1; l2++)
        {
            for (j=1; j<=M; j++)
            {
                V[j]=1LL*V[j-1]+SUM[l2][j]-SUM[l1-1][j]-1LL*X*(l2-l1+1);
                Min[j]=min(Min[j-1],V[j]);
                if (j>=C)
                    if (V[j]-Min[j-C]>=0) return 1;
            }
        }
    return 0;
}

void Solve ()
{
    int P=0,U=MX,M;
    while (P<=U)
    {
        M=(P+U)>>1;
        if (Check(M))
        {
            ANS=M;
            P=M+1;
        }
        else
            U=M-1;
    }
}

void Print ()
{
    g << fixed << setprecision(3) << (1.0*ANS/1000.0) << '\n';
    g.close();
}

int main ()
{
    Read();
    Solve();
    Print();
    return 0;
}