Cod sursa(job #938603)

Utilizator SteveStefan Eniceicu Steve Data 13 aprilie 2013 00:06:49
Problema Balans Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

int N, M, R, C;
int mat[311][311];
double v[311];
deque <pair <double, int> > Dq;

void Citire ()
{
    ifstream fin ("balans.in");
    fin >> N >> M >> R >> C;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            fin >> mat[i][j];
            mat[i + N][j] = mat[i][j];
            mat[i][j + M] = mat[i][j];
            mat[i + N][j + M] = mat[i][j];
        }
    }
    fin.close ();
    for (int i = 1; i <= (N << 1); i++)
        for (int j = 1; j <= (M << 1); j++)
            mat[i][j] += mat[i - 1][j];
}

bool Good (int a, int b, double K)
{
    for (int i = 1; i <= (N << 1); i++)
        v[i] = v[i - 1] + mat[b][i] - mat[a - 1][i] - (b - a + 1) * K;
    Dq.clear ();
    for (int i = C; i <= (N << 1); i++)
    {
        while (!Dq.empty () && i - Dq.front ().second > M) Dq.pop_front ();
        while (!Dq.empty () && Dq.back ().first > v[i - C]) Dq.pop_back ();
        Dq.push_back (make_pair (v[i - C], i - C));
        if (v[i] - Dq.front ().first >= 0) return 1;
    }
    return 0;
}

double B_Search (int a, int b)
{
    double val = 0;
    for (double step = 100000; step >= 0.0001; step /= 2)
        if (Good (a, b, step + val)) val += step;
    return val;
}

double Business ()
{
    double Ans = -1;
    for (int a = 1; a <= N; a++)
    {
        for (int b = a + R - 1; b < a + N; b++)
        {
            double local = B_Search (a, b);
            if (local > Ans) Ans = local;
        }
    }
    return Ans;
}

void Scriere ()
{
    ofstream fout ("balans.out");
    fout << fixed << setprecision (3) << Business ();
    fout.close ();
}

int main ()
{
    Citire ();
    Scriere ();
    return 0;
}