Cod sursa(job #676960)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 februarie 2012 19:01:49
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <algorithm>

#define NMax 305
#define Infinity 100000000

using namespace std;

int N, M, R, C, D[NMax], A[NMax][NMax];
long long SumC[NMax][NMax];
double Solution;

inline long long MSS (long long Sum[])
{
    long long SMax=Sum[C];
    int F=1, B=0;
    D[1]=0;
    for (int i=C; i<=M+M; ++i)
    {
        while (F<=B and D[F]<i-M)
        {
            ++F;
        }
        while (F<=B and Sum[i-C]<=Sum[D[B]])
        {
            --B;
        }
        D[++B]=i-C;
        SMax=max (SMax, Sum[i]-Sum[D[F]]);
    }
    return SMax;
}

inline void BuildSum (long long Sum[], int L1, int L2, long long S)
{
    Sum[0]=0;
    for (int i=1; i<=M+M; ++i)
    {
        Sum[i]=Sum[i-1]+SumC[L2][i]-SumC[L1-1][i]-(L2-L1+1)*S;
    }
}

inline bool FindMSM (long long S)
{
    long long Sum[NMax];
    for (int L1=1; L1<=N; ++L1)
    {
        for (int L2=L1+R-1; L2<=L1+N-1; ++L2)
        {
             BuildSum (Sum, L1, L2, S);
             if (MSS (Sum)>=0)
             {
                 return true;
             }
        }
    }
    return false;
}

void Solve ()
{
    long long L=0, R=Infinity;
    while (L<=R)
    {
        long long Mid=(L+R)/2;
        if (FindMSM (Mid))
        {
            Solution=Mid;
            L=Mid+1;
        }
        else
        {
            R=Mid-1;
        }
    }
}

void Read ()
{
    freopen ("balans.in", "r", stdin);
    scanf ("%d %d %d %d", &N, &M, &R, &C);
    if (R==0) R=1;
    if (C==0) C=1;
    for (int i=1; i<=N; ++i)
    {
        for (int j=1; j<=M; ++j)
        {
            scanf ("%d", &A[i][j]);
            A[i][j]*=1000;
            A[i+N][j]=A[i][j+M]=A[i+N][j+M]=A[i][j];
        }
    }
    for (int i=1; i<=N+N; ++i)
    {
        for (int j=1; j<=M+M; ++j)
        {
            SumC[i][j]=SumC[i-1][j]+A[i][j];
        }
    }
}

void Print ()
{
    freopen ("balans.out", "w", stdout);
    printf ("%.3lf\n", (Solution*1.0)/1000);
}

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