Cod sursa(job #318267)

Utilizator CezarMocanCezar Mocan CezarMocan Data 27 mai 2009 20:40:14
Problema Balans Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <cstdio>
#include <cstring>
#define maxn 311

using namespace std;

long long c[maxn], t[maxn];
int n, m, i, j, l, u, ro, co;
long long sum[maxn], rez;
long long p[maxn];
int deq[maxn], sus, jos;
int v[maxn][maxn];
long long col[maxn][maxn];


inline bool posibil(int d, int n) {
	int i, j;
	for (i = 1; i <= n; i++) 
		p[i] = c[i] - (t[i] * d);

	for (i = 1; i <= n; i++) 
		sum[i] = sum[i - 1] + p[i];

	sus = 0; jos = 1;
	memset(deq, 0, sizeof(deq));
	for (i = 1; i <= n; i++) {
		if (i - l > 0) {
			while (sum[i - l] < sum[deq[sus]] && sus >= jos)
				sus--;
			sus++;
			deq[sus] = i - l;
		}
		while (deq[jos] < i - u && jos <= sus)
			jos++;

		if (sum[i] - sum[deq[jos]] >= 0 && deq[jos] != 0)
			return true;
	}

	return false;

}

inline bool se_poate(int d) {
    int l1, l2, i;
    bool ok = 0;   
    
    for (l1 = 1; l1 <= n; l1++)
        for (l2 = l1 + ro - 1; l2 <= n; l2++)
            if (l2 - l1 <= n) {
                for (i = 1; i <= m; i++) {
                    c[i] = col[l2][i] - col[l1 - 1][i];
                    t[i] = l2 - l1 + 1;   
                }
                
                if (posibil(d, m))
                    return true;
            }
            else
                break;
                
    return false;
}

void bsearch(int left, int right) {
	int m;
	while (left <= right) {
		m = (left + right) >> 1;
		if (se_poate(m)) {
			if (m > rez)
				rez = m;
			left = m + 1;
		}
		else
			right = m - 1;
	}
}

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

	scanf("%d%d%d%d", &n, &m, &ro, &co);
	l = co; u = m;
//	fprintf(stderr, "%d\n", m);
	
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            scanf("%d", &v[i][j]);
            v[i][j] = v[i][j] * 1000;
            v[i + n][j] = v[i][j + m] = v[i + n][j + m] = v[i][j];
        }
        
    n = 2 * n; m = 2 * m;
            
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) 
            col[i][j] = col[i - 1][j] + v[i][j];
            
	bsearch(0, 200000000);
	printf("%lld.", rez / 1000);
	if (rez % 1000 == 0) {
        printf("000\n");
        return 0;   
    }
	while (rez * 10 < 1000)
	   printf("0");
    printf("%lld\n", rez % 1000); 	

	return 0;
}