Cod sursa(job #403608)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 25 februarie 2010 09:32:44
Problema Balans Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <algorithm>
#define MAXN 160

using namespace std;

long long a[MAXN*2][MAXN*2];
long long v[MAXN*2], s[MAXN*2], d[MAXN*2];
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++){
		while (back >= front && s[d[back]]>s[i-c]) back--;
		d[++back] = i-c;
		if (d[front] < i-m) front ++;
		rez = max(rez, s[i] - s[d[front]]);
	}
	return rez;
}

inline void caut(long long st, long long dr)
{
	long long mij;
	while (st<=dr){
		mij = (st+dr)/2;
		if (calc(mij)>=0){
			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++){
		memset(v,0,sizeof(v));
		for (i=lung; i<n+lung; i++){
			for (j=1; j<=2*m; j++)
				v[j] =(long long) a[i][j] - a[i-lung][j];
			caut(sol,dr);
		}
	}
	long long rez1 = sol/1000;
	long long rez2 = sol%1000;
	v[1]=v[2]=v[3]=0;
	for (j=1; j<=3; j++, rez2/=10)
		v[j] = rez2%10;
	printf("%Ld.",rez1);
	for (j=3; j>=1; j--)
		printf("%Ld",v[j]);
	printf("\n");
	fclose(stdin); fclose(stdout);
	return 0;
}