Cod sursa(job #1941851)

Utilizator borcanirobertBorcani Robert borcanirobert Data 27 martie 2017 17:01:20
Problema Balans Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;

ifstream fin("balans.in");
ofstream fout("balans.out");

const int MAX = 310;
using LL = long long;
LL a[MAX][MAX];
LL N, M;
LL P, Q;
LL sc[MAX][MAX];
LL v[MAX];
LL maxim;
deque<LL> D;

void Read();
LL BinarySearch();
bool Check( LL v );
bool Deque( vector<LL>& s );

int main()
{
    Read();

    fout << fixed << setprecision(3) << BinarySearch() / 1000. << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> N >> M >> P >> Q;
    for ( LL i = 1; i <= N; ++i )
        for ( LL j = 1; j <= M; ++j )
            fin >> a[i][j];

    for ( LL i = 1; i <= N; ++i )
        for ( LL j = 1; j <= M; ++j )
        {
            a[i + N][j] = a[i][j + M] = a[i + N][j + M] = a[i][j] = a[i][j] * 1000;
            maxim = max( maxim, a[i][j] );
        }
    N *= 2, M *= 2;

 /*   for ( LL i = 1; i <= N; ++i )
    {
        for ( LL j = 1; j <= M; ++j )
        {
            sc[i][j] = sc[i - 1][j] + a[i][j];
           // fout << a[i][j] << ' ';
        }

     //   fout << '\n';
    }   */
}

LL BinarySearch()
{
    LL st = 1, dr = maxim, mij, r{0};

    while ( st <= dr )
    {
        mij = st + ( dr - st ) / 2LL;

        if ( Check(mij) )
        {
            r = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }

    return r;
}

bool Check( LL v )
{
    LL i1, i2, i, j;
    bool ok{false};
    vector<LL> s(M + 1);

    for ( i = 1; i <= N; ++i )
        for ( j = 1; j <= M; ++j )
        {
            a[i][j] -= v;
            sc[i][j] = sc[i - 1][j] + a[i][j];
        }

    for ( i1 = 1; i1 <= (N >> 1) && !ok; ++i1 )
        for ( i2 = i1 + P - 1; i2 <= i1 + ( N >> 1 ) && !ok; ++i2 )
        {
            for ( j = 1; j <= M; ++j )
                s[j] = s[j - 1] + ( sc[i2][j] - sc[i1 - 1][j] );

            if ( Deque(s) )
                ok = true;
        }

    for ( i = 1; i <= N; ++i )
        for ( j = 1; j <= M; ++j )
            a[i][j] += v;

    return ok;
}

bool Deque( vector<LL>& s )
{
    D.clear();
    LL i;

    for ( i = Q; i <= M; ++i )
    {
        while ( !D.empty() && s[i - Q] <= s[D.back()] )
            D.pop_back();
        D.push_back(i - Q);

        if ( s[i] - s[D.front()] >= 0 )
            return true;
    }

    return false;
}