Cod sursa(job #676902)

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

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

using namespace std;

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

inline double MSS (double X[])
{
    deque <int> D;
    double Sum[NMax], SMax=-AMax;
    Sum[0]=0;
    for (int i=1; i<C; ++i)
    {
        Sum[i]=Sum[i-1]+X[i];
    }
    for (int i=C; i<=M+M; ++i)
    {
        Sum[i]=Sum[i-1]+X[i];
        while (!D.empty () and D.front ()<i-M)
        {
            D.pop_front ();
        }
        while (!D.empty () and Sum[i-C]<=Sum[D.back ()])
        {
            D.pop_back ();
        }
        D.push_back (i-C);
        SMax=max (SMax, Sum[i]-Sum[D.front ()]);
    }
    return SMax;
}

inline void BuildX (double X[], int L1, int L2, double S)
{
    for (int i=1; i<=M+M; ++i)
    {
        X[i]=(double)SumC[i][L2]-(double)SumC[i][L1-1]-(double)(L2-L1+1)*S;
    }
}

inline bool FindMSM (double S)
{
    double X[NMax];
    for (int L1=1; L1<=N+N; ++L1)
    {
        for (int L2=L1+R-1; L2<=N+N and L2<=L1+N-1; ++L2)
        {
             BuildX (X, L1, L2, S);
             if (MSS (X)>=-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 j=1; j<=M+M; ++j)
    {
        for (int i=1; i<=N+N; ++i)
        {
            SumC[j][i]=SumC[j][i-1]+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;
}