Cod sursa(job #317808)

Utilizator savimSerban Andrei Stan savim Data 25 mai 2009 11:30:20
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>

#define MAX_N 310

int n, m, r, c, i, j, k, p, q, ok, sol;
int A[MAX_N][MAX_N], deque[MAX_N];
int st, dr, mid;
long long sum[MAX_N][MAX_N], suma[MAX_N];

void cit() {
	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("%d", &A[i][j]);
			if (A[i][j] > dr) dr = A[i][j];
		}

	for (i = 1; i <= 2 * n; i++)
		for (j = 1; j <= 2 * m; j++)
			if (i > n || j > m) {
				int p = i % n; q = j % m;
                if (p == 0) p = n;
				if (q == 0) q = m;

				A[i][j] = A[p][q];
			}

	for (i = 1; i <= 2 * n; i++)
		for (j = 1; j <= 2 * m; j++)
			sum[i][j] = sum[i - 1][j] + A[i][j] * 1000;
}                             

void solve() {  
	st = 0;	dr = 1000000001; mid = 0;
	while (st + 1 < dr) {
		mid = (st + dr) / 2;

        //imi trebuie submatricea de suma maxima cu dimensiuni >= (R, C)
		ok = 0;
		for (i = 1; i <= n; i++) {
			for (j = i + r - 1; j <= 2 * n; j++) {
            	if (j - i + 1 > n) break;

                for (k = 1; k <= 2 * m; k++)
					suma[k] = suma[k - 1] + (sum[j][k] - sum[i - 1][k] - (j - i + 1) * mid);

				//am fixat doua linii, problema revenind la determinarea subsecventei de suma maxima cu lungime > C si < M
				p = 1; q = 0;
				for (k = 1; k <= 2 * m; k++) {
					if (k - c > 0) { //adaug in deque elementeul K - C
						deque[++q] = k - c;
						while (suma[deque[q]] < suma[deque[q - 1]] && q > p) {
							deque[q - 1] = deque[q];
							q--;
						}
                        
						while (deque[p] < k - m + 1 && p < q) p++;

						if (suma[k] - suma[deque[p]] >= 0) {
							ok = 1;
							break;
						}
					}
				}
				if (ok) break;
			}
			if (ok) break;
		}

		if (ok) {
			if (mid > sol) sol = mid;
			st = mid;
		}
		else dr = mid;
	}

	printf("%d.%d\n", sol/1000, sol%1000);
}

int main() {

    cit();
	solve();

	return 0;
}