Cod sursa(job #1941758)

Utilizator borcanirobertBorcani Robert borcanirobert Data 27 martie 2017 16:16:18
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 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];
int N, M;
int P, Q;
LL sc[MAX][MAX];
LL v[MAX];
LL maxim;

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

int main()
{
    Read();

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

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

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

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

    for ( int i = 1; i <= N; ++i )
    {
        for ( int 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 ) / 2;

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

    return r;
}

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

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

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

    return ok;
}

bool Deque( vector<LL>& s )
{
    deque<int> D;
    int 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;
}