Cod sursa(job #1843166)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 8 ianuarie 2017 12:42:48
Problema Balans Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;


const int Nmax = 303;

int N, M, R, C, i, j, st, dr, mid;
long long a[Nmax][Nmax], b[Nmax];

bool good()
{
    deque<int> dq;
    int i;

    for(i=C; i<=2*M; ++i)
    {
        if(dq.size() && dq.front()==i-M-1) dq.pop_front();
        while(dq.size() && b[dq.back()] >= b[i-C]) dq.pop_back();
        dq.push_back(i-C);

        if(b[i] - b[dq.front()] >= 0) return 1;
    }

    return 0;
}

bool check(int x)
{
    int i, j, k;

    for(i=1; i<=2*N; ++i)
        for(j=i+R-1; j<=i+N-1 && j<=2*N; ++j)
        {
            for(k=1; k<=2*M; ++k)
                b[k] = b[k-1] + a[j][k] - a[i-1][k] - 1LL*x*(j-i+1);
            if(good()) return 1;
        }

    return 0;
}

int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);

    scanf("%d%d%d%d", &N, &M, &R, &C);

    for(i=1; i<=N; ++i)
        for(j=1; j<=M; ++j)
            scanf("%lld", &a[i][j]);

    for(i=1; i<=2*N; ++i)
        for(j=1; j<=2*M; ++j)
            a[i][j] = a[i<=N ? i : i-N][j<=M ? j : j-M];

    for(i=1; i<=2*N; ++i)
        for(j=1; j<=2*M; ++j)
            a[i][j] = a[i-1][j] + 1000*a[i][j];

    st=0; dr=1e8;
    while(st<=dr)
    {
        mid = (st+dr)/2;
        if(check(mid)) st = mid+1;
        else dr = mid-1;
    }

    printf("%.3lf\n", (double)dr/1000);

    return 0;
}