Cod sursa(job #317811)

Utilizator savimSerban Andrei Stan savim Data 25 mai 2009 11:35:28
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;
int A[MAX_N][MAX_N], sum[MAX_N][MAX_N], deque[MAX_N];
double suma[MAX_N];
double st, dr, mid, sol;

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];
}

void solve() {  
	st = 0;	dr = 1000000000; mid = 0;
	while (st + 0.0001 < dr) {
		mid = (double) (st + dr) / 2;

        //imi trebuie submatricea de suma maxima cu dimensiuni >= (R, C)
		ok = 0;
		for (i = 1; i <= 2 * 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] + double (sum[j][k] - sum[i - 1][k] - (j - i + 1) * mid) / (j - i + 1);

				//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 (deque[p] && 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("%.3lf\n", sol);
}

int main() {

    cit();
	solve();

	return 0;
}