Cod sursa(job #800762)

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

const int N = 320;

int n, m, p, q, x[N][N], bmax, mx;
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() {
    long long smax = -10000, d[N];
	int i, p = 1, u = 0;

	for(i = 1; i + q<=m; ++i) {
		
		while(p <= u && i + q - d[p] >= m/2)
			++p;
		
		while(p <= u && v[d[u]] >= v[i])
			--u;
		d[++u] = i;
		
		smax = max(smax, v[i + q] - v[d[p]]);
		if(smax >= 0)
			return 1;
	}
	
    return 0;
}

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

    for(i = 0; pas; pas>>=1) if(i + pas <= mx && i + 2*pas - 1 > bmax) {

        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, mx = max(mx, x[i][j]);

    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/2; ++i)
        for(j = i + p - 1; j<i + n/2; ++j)
            calc(i, j);

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

    return 0;
}