Cod sursa(job #676958)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 februarie 2012 18:55:38
Problema Balans Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <cstdio>
#include <algorithm>

#define NMax 305
#define AMax 100001
#define Eps 1e-7

using namespace std;

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

inline double MSS (double Sum[])
{
    double SMax=Sum[C];
    int F=1, B=0;
    D[1]=1;
    for (int i=C+1; i<=M+M; ++i)
    {
        while (F<=B and D[F]+M<i)
        {
            ++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 (double Sum[], int L1, int L2, double S)
{
    Sum[0]=0;
    for (int i=1; i<=M+M; ++i)
    {
        Sum[i]=Sum[i-1]+SumC[L2][i]-SumC[L1-1][i]-(double)(L2-L1+1)*S;
    }
}

inline bool FindMSM (double S)
{
    double 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)>=-Eps)
             {
                 return true;
             }
        }
    }
    return false;
}

void Solve ()
{
    double L=0, R=AMax;
    while (L+Eps<=R)
    {
        double Mid=(L+R)/2;
        if (FindMSM (Mid))
        {
            Solution=Mid;
            L=Mid+Eps;
        }
        else
        {
            R=Mid-Eps;
        }
    }
}

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+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);
    Solution=(double)((int)(Solution*1000))/1000.0;
    printf ("%.3lf\n", Solution);
}

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