Cod sursa(job #404173)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 25 februarie 2010 21:04:54
Problema Balans Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <algorithm>
#define MAXN 512

using namespace std;

long long a[MAXN][MAXN];
long long v[MAXN], s[MAXN], d[MAXN];
int i,j,n,m,r,c, lung;
long long sol,dr;

inline long long calc(long long w)
{
	int i;
	for (i=1; i<=2*m; i++)
		s[i] = s[i-1] + v[i] - w*lung;
	int front = 1;
	int back = 0;
	long long rez = -1;
	for (i=c; i< 2*m; i++){
		for (; back >= front && s[d[back]]>s[i-c]; back--);
		d[++back] = i-c;
		if (d[front] < i-m) front ++;
		if (rez < s[i] - s[d[front]])  
			rez = s[i] - s[d[front]];
		rez = max(rez, s[i] - s[d[front]]);
	}
	return rez;
}

inline bool calc2(long long w)
{
	for (lung = r; lung<=n; lung++)
		for (i=lung; i<n+lung; i++){
			for (j=1; j<=2*m; j++)
				v[j] =a[i][j] - a[i-lung][j];
			if (calc(w)>=0) return true;
		}
	return false;
}
inline void caut(long long st, long long dr)
{
	long long mij;
	while (st<=dr){
		mij = (st+dr)/2;
		if (calc2(mij)){
			sol=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	}
}
int main()
{
	freopen("balans.in","r",stdin);
	freopen("balans.out","w",stdout);
	scanf("%d %d",&n,&m);
	scanf("%d %d",&r,&c);
	dr=0;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++){
			scanf("%Ld",&a[i][j]);
			a[i][j]*=1000;
			if (a[i][j]>dr) dr=a[i][j];
			a[i][j] += a[i-1][j];
			a[i][j+m] = a[i][j];
		}
	for (i=n+1; i<=2*n; i++)
		for (j=1; j<=m; j++){
			a[i][j] = a[n][j] + a[i-n][j];
			a[i][j+m] = a[i][j];
		}
	for (lung = r; lung<=n; lung++){
		for (i=lung; i<n+lung; i++){
			for (j=1; j<=2*m; j++)
				v[j] =a[i][j] - a[i-lung][j];
		}
	}
	caut(0,dr);
	printf("%Ld.",sol/1000);
	sol%=1000;
	if (sol>=100) printf("%Ld",sol);
	else
		if (sol>=10) printf("0%Ld",sol);
		else printf("00%Ld",sol);
	printf("\n");
	fclose(stdin); fclose(stdout);
	return 0;
}