Cod sursa(job #800747)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 22 octombrie 2012 15:20:38
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 320;

int n, m, p, q, x[N][N], bmax;
long long s[N][N], v[N];

inline long long max(const long long &a, const long long &b) {
    return (a > b ? a : b);
}

bool ver() {
    int i;
    long long smax = -10000, d[N];

    d[0] = 0;

    for(i = 1; i<=m; ++i)
        d[i] = max(v[i] - v[i - 1], d[i - 1] + v[i] - v[i - 1]);

    for(i = q; i<=m; ++i)
        smax = max(max(smax, v[i] - v[i - q]), d[i - q] + v[i] - v[i - q]);
    return smax >= 0;
}

void calc(int l1, int l2) {
    int j, i, pas = 1<<30;

    for(i = 0; pas; pas>>=1) {

        for(j = 1; j<=m; ++j)
            v[j] = (s[l2][j] - s[l1 - 1][j]) - (long long)(l2 - l1 + 1)*(i + pas) + v[j - 1];

        if(ver())
            i += pas;
    }
    bmax = max(bmax, i);
}

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

    cin >> n >> m >> p >> q;

    for(i = 1; i<=n; ++i)
        for(j = 1; j<=m; ++j)
            cin >> x[i][j], x[i][j] *= 1000;

    for(i = 1; i<=n; ++i)
        for(j = 1; j<=m; ++j)
            x[i][j + m] = x[i][j];
    m*=2;

    for(i = 1; i<=n; ++i)
        for(j = 1; j<=m; ++j)
            x[i + n][j] = x[i][j];
    n*=2;

    for(j = 1; j<=m; ++j)
        for(i = 1; i<=n; ++i)
            s[i][j] = s[i - 1][j] + x[i][j];

    for(i = 1; i<=n - p + 1; ++i)
        for(j = i + p - 1; j<i + n/2; ++j)
            calc(i, j);

    printf("%.3f", (double)bmax / 1000);

    return 0;
}