Cod sursa(job #1843171)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 8 ianuarie 2017 12:48:54
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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()
{
    int i, p1=1, p2=0, dq[Nmax];

    for(i=C; i<=2*M; ++i)
    {
        if(p1<=p2 && dq[p1]==i-M-1) ++p1;
        while(p1<=p2 && b[dq[p2]] >= b[i-C]) --p2;
        dq[++p2] = i-C;

        if(b[i] >= b[dq[p1]]) 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;
}