Cod sursa(job #394479)

Utilizator ProtomanAndrei Purice Protoman Data 10 februarie 2010 23:14:21
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <algorithm>
#include <stdio.h>

#define ll long long
#define MAX 511

using namespace std;

int n, m, r, c, pos, lung, sol, mv;
ll suma[MAX], s[MAX];
int deqMin[MAX];
int a[MAX][MAX];

inline int max(ll x, ll y)
{
	if (x > y)
		return x;
	return y;
}

inline ll calc(int x)
{
	for (int i = 1; i <= 2 * m; i++)
		s[i] = s[i - 1] + suma[i] - x * lung;

	int deqSt = 1, deqSf = 0;
	ll maxGs = -1;
	for (int i = 1; i < 61; i++)
		maxGs *= (ll) 2;
	for (int i = c; i <= 2 * m; i++)
	{
		deqMin[++deqSf] = i - c;

		for (; deqSf > 1 && s[deqMin[deqSf]] < s[deqMin[deqSf - 1]]; deqSf--)
			swap(deqMin[deqSf], deqMin[deqSf - 1]);
		if (deqMin[deqSt] <= i - m)
			deqSt++;

		maxGs = max(maxGs, s[i] - s[deqMin[deqSt]]);
	}

	return maxGs;
}

inline void cautaBin(int st, int dr)
{
	if (st > dr)
		return;
	int med = (st + dr) / 2;

	if (calc(med) >= 0)
	{
		pos = med;
		cautaBin(med + 1, dr);
	}
	else cautaBin(st, med - 1);
}

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

	scanf("%d %d %d %d", &n, &m, &r, &c);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
			a[i][j] *= 1000;
			mv = max(mv, a[i][j]);
			a[n + i][j] = a[i][m + j] = a[n + i][m + j] = a[i][j];
		}

	for (lung = r; lung <= n; lung++)
	{
		memset(suma, 0, sizeof(suma));
		for (int i = 1; i < lung; i++)
			for (int j = 1; j <= 2 * m; j++)
				suma[j] += (ll) a[i][j];

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= 2 * m; j++)
				suma[j] += (ll) a[i + lung][j] - a[i - 1][j];
			
			cautaBin(0, mv);
			sol = max(sol, pos);
		}
	}

	printf("%.3lf\n", (double) sol / 1000);

	fclose(stdin);
	fclose(stdout);
	return 0;
}