Cod sursa(job #1413900)

Utilizator stefanzzzStefan Popa stefanzzz Data 2 aprilie 2015 10:41:56
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <deque>
#define MAXN 160
#define MAXVAL 100005
#define INF 2000000000000000000
using namespace std;

int n, m, r, c, a[2 * MAXN][2 * MAXN], i1, i2;
long long Sp[2 * MAXN][2 * MAXN];

inline long long val(int j){
	return Sp[i2][j] - Sp[i1 - 1][j];
}

bool works(int x){
	int i, j;
	long long maxS = -INF;
	deque<int> dq;

	for(i = 1; i <= 2 * n; i++)
		for(j = 1; j <= 2 * m; j++)
			Sp[i][j] = Sp[i - 1][j] + Sp[i][j - 1] - Sp[i - 1][j - 1] + a[i][j] - x;
	
	/*printf("%d:\n", x);
	for(i = 1; i <= 2 * n; i++, printf("\n"))
		for(j = 1; j <= 2 * m; j++)
			printf("%8lld ", Sp[i][j]); */

	for(i1 = 1; i1 <= 2 * n; i1++)
		for(i2 = i1 + r - 1; i2 <= 2 * n && i2 - i1 + 1 <= n; i2++){
			dq.clear();
			for(j = c; j <= 2 * m; j++){
				while(!dq.empty() && val(j - c) < val(dq.back()))	dq.pop_back();
				dq.push_back(j - c);

				while(j - dq.front() > m) dq.pop_front();
				 
				if(val(j) - val(dq.front()) > maxS) maxS = val(j) - val(dq.front());
			}
		}
	
	//printf("%lld\n\n", maxS);
	return maxS >= 0;
}
				 

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

	int i, j;
	
	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]);
			a[i][j] *= 1000;
		}
	
	for(i = n + 1; i <= 2 * n; i++)
		for(j = 1; j <= m; j++)
			a[i][j] = a[i - n][j];
	
	for(i = 1; i <= n; i++)
		for(j = m + 1; j <= 2 * m; j++)
			a[i][j] = a[i][j - m];
	
	for(i = n + 1; i <= 2 * n; i++)
		for(j = m + 1; j <= 2 * m; j++)
			a[i][j] = a[i - n][j - m];
		
	int l = 0, r = MAXVAL * 1000, mid;
	
	while(l < r){
		mid = (l + r) >> 1;
		if(works(mid)) l = mid + 1;
		else r = mid - 1;
	}
	while(!works(l)) l--;

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

	return 0;
}