Cod sursa(job #494101)

Utilizator ConsstantinTabacu Raul Consstantin Data 20 octombrie 2010 19:28:38
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
int a[ 310 ][ 310 ],n,m,r,c,i,j,k,l,p,u,dp[ 310 ];
double d[ 310 ],bmax;
void citire(){
freopen("balans.in","r",stdin);
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]);
	
}

double medie(int i1,int j1,int i2,int j2){
int s,n;
s = a[i2][j2] - a[i1-1][j2] - a[i2][j1-1]+a[i1-1][j1-1];
n = (i2- i1+1)*(j2-j1+1);
return (double)(s)/(double)(n);
}

int bs(double val,int u,int p){
int m,sol = 0;
while(p<=u)
	{m = (p+u)>>1;
	if(d[m] < val)
		{sol = m;
		p = m+1;
		}
	else
		u = m-1;
	}
return dp[sol];
}
void check(int i,int ii){
int p = 1,u=0;
d[0] = dp[0] = 0;
double MC,poz;
d[1] = medie(i,1,ii,1);
dp[1] = 1;

if(d[1]>bmax)
	bmax = d[1];

for(int j = c+1 ; j <= m ; j++)
	{
	MC = medie(i,1,ii,j-c);
	while(MC < d[p])
		p--;
	p++;
	d[p] = MC;
	dp[p] = j-c;
	
	MC = medie(i,1,ii,j);
	
	while(j - dp[u] > (m>>1) )u++;
	
	poz = bs(MC,p,u);
	
	if(!poz)
		poz = j - (m>>1);
	
	
	MC = medie(i,poz+1,ii,j);
	if(MC > bmax)
		bmax = MC;
	}
}

void solve(){
for(i = 1; i <= n ; i++)
	for(j = 1 ; j <= m ; j++)
		a[i+n][j] = a[i][j+m] = a[i+n][j+m] = a[i][j];
	
n = n<<1;
m = m<<1;

for(i=1;i<=n;i++)
	for(j = 1 ; j <= m ; j++)
		a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
int ii;
for(i = 1; i <= n ; i++)
	for(ii = i+r-1 ; ii <= n && (ii - i+1 <= (n>>1)) ; ii++)
		check(i,ii);

}
void afisare(){
freopen("balans.out","w",stdout);
printf("%0.3f",bmax);
}
int main(){
citire();
solve();
afisare();
return 0;
}