Cod sursa(job #938621)

Utilizator SteveStefan Eniceicu Steve Data 13 aprilie 2013 02:21:34
Problema Balans Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <iomanip>

using namespace std;

int N, M, R, C;
int mat[311][311];
char pars[1111];
long long v[311];
int Dq[1161];

void Citire ()
{
    ifstream fin ("balans.in");
    fin >> N >> M >> R >> C;
    fin.getline (pars, 10);
    for (int i = 1; i <= N; i++)
    {
        fin.getline (pars, 1101);
        int a = 0, K = 0;
        for (int j = 0; pars[j] != '\0'; j++)
        {
            if (pars[j] >= '0' && pars[j] <= '9') a = a * 10 + pars[j] - '0';
            else
            {
                mat[i][++K] = a;
                a = 0;
                mat[i + N][K] = mat[i][K];
                mat[i][K + M] = mat[i][K];
                mat[i + N][K + M] = mat[i][K];
            }
        }
    }
    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];
}

int Good (int a, int b, int K)
{
    for (int i = 1; i <= (M << 1); i++)
        v[i] = v[i - 1] + 1LL * 1000 * (mat[b][i] - mat[a - 1][i]) - 1LL * (b - a + 1) * K;
    int front = 0, marime = 1;
    Dq[0] = 0;
    if (v[C] >= 0) return 1;
    for (int i = C + 1; i <= (M << 1); i++)
    {
        while (marime && i - Dq[front] > M) front++, marime--;
        while (marime && v[Dq[front + marime - 1]] > v[i - C]) marime--;
        Dq[front + marime] = i - C;
        if (v[i] - v[Dq[front]] >= 0) return 1;
    }
    return 0;
}

int B_Search (int a, int b)
{
    int val = 0;
    for (int step = 1 << 26; step; step >>= 1)
        if (Good (a, b, step + val)) val += step;
    return val;
}

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

void Scriere ()
{
    ofstream fout ("balans.out");
    int Ans = Business ();
    int zec = Ans % 1000;
    fout << Ans / 1000 << ".";
    if (zec < 10) fout << "00";
    else if (zec < 100) fout << "0";
    fout << zec;
    fout.close ();
}

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