Cod sursa(job #1068526)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 decembrie 2013 14:08:47
Problema Balans Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

const int Nmax = 302;

int N, M, R, C;

deque <int> deck;

int A[Nmax][Nmax];
long long sum[Nmax][Nmax];
long long sume_coloana[Nmax];
long long sumCol[Nmax];

int valid( int cost )
{
    for ( int i = 1; i <= 2 * N; ++i )
    {
        for ( int j = i + R - 1; j - i < N && j <= 2 * N; ++j )
        {
            for ( int k = 1; k <= 2 * M; ++k )
            {
                sume_coloana[k] = sum[j][k] - sum[i - 1][k] - 1LL * cost * ( j - i + 1 );
                sumCol[k] = sumCol[k - 1] + sume_coloana[k];
            }

            deck.clear();

            for ( int k = C; k <= 2 * M; ++k )
            {
                while ( deck.size() && sumCol[ deck.back() ] > sumCol[k - C] ) deck.pop_back();
                while ( deck.size() && deck.front() < k - M ) deck.pop_front();

                deck.push_back( k - C );

                if ( sumCol[k] >= sumCol[ deck.front() ] )
                        return 1;
            }
        }
    }

    return 0;
}

int cautare_binara()
{
    int st = 0;
    int dr = 100001 * 1000;
    int sol = 0;
    int m;

    while ( st <= dr )
    {
        m = ( st + dr ) / 2;

        if ( valid( m ) )
        {
            st = m + 1;
            sol = m;
        }
        else
        {
            dr = m - 1;
        }
    }

    return sol;
}

const int DIM_BUFF = ( 1 << 20 );

char buffer[DIM_BUFF];
int position = DIM_BUFF;

char GetChar()
{
    if ( position == DIM_BUFF )
    {
        fread( buffer, 1, DIM_BUFF, stdin );
        position = 0;
    }

    return buffer[ position++ ];
}

int rd()
{
    int nr = 0;
    char c;

    do
    {
        c = GetChar();

    } while ( !isdigit( c ) );

    do
    {
        nr = nr * 10 + ( c - '0' );
        c = GetChar();

    } while ( isdigit( c ) );

    return nr;
}

int main()
{
    freopen("balans.in", "r", stdin);
    ofstream g("balans.out");

    N = rd(); M = rd(); R = rd(); C = rd();

    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= M; ++j )
            {
                A[i][j] = rd();

                A[i][j] *= 1000;
                A[i + N][j] = A[i][j + M] = A[i + N][j + M] = A[i][j];
            }

    for ( int i = 1; i <= 2 * N; ++i )
    {
        for ( int j = 1; j <= 2 * N; ++j )
        {
            sum[i][j] = sum[i - 1][j] + A[i][j];
        }
    }

    g << fixed << setprecision( 3 );
    g << (double)cautare_binara() / 1000;

    return 0;
}