Cod sursa(job #395187)

Utilizator ProtomanAndrei Purice Protoman Data 12 februarie 2010 13:24:41
Problema Balans Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <algorithm>
#include <stdio.h>

#define ll long long
#define MAX 512

using namespace std;

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

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

inline ll calc(ll 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 = c; i <= 2 * m; i++)
	{
		deqMin[++deqSf] = i - c;

		for (; deqSf > deqSt && 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("%lld", &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 (int i = 1; i <= 2 * n; i++)
		for (int j = 1; j <= 2 * m; j++)
			a[i][j] += a[i - 1][j];

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

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

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