Cod sursa(job #384212)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 19 ianuarie 2010 18:34:38
Problema Balans Scor 25
Compilator c Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<stdio.h>
#define infile "balans.in"
#define outfile "balans.out"
#define nmax 313
#define vmax (100*1001)
int a[nmax][nmax]; //matricea initiala
int n,m; //numarul de linii respectiv coloane
int nn,mm; //dubmlul nr-ului de linii, respectiv coloane
int lin,col; //numarul minim de randuri respectiv coloane
double med; //media maxima

void read()
{
	int i,j;
	scanf("%d %d %d %d\n",&n,&m,&lin,&col);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d\n",&a[i][j]);
}

void init()
{
	int i,j;
	
	//punem matricea in dreapta, in jos, si in dreapta jos
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			a[i][m+j]=a[n+i][j]=a[n+i][m+j]=a[i][j];
	
	//dublam numarul de linii si coloane
	nn=n<<1;
	mm=m<<1;
}

int verif(double med)
{
	double b[nn+1][mm+1]; //b[i][j]=b[1][j]+a[i][j]-med
	int i,j,k;
	
	//construim b[]-ul
	for(i=0;i<=mm;i++) b[0][i]=0;
	for(i=1;i<=nn;i++)
		for(b[i][0]=0,j=1;j<=mm;j++)
			b[i][j]=b[i-1][j]+(double)a[i][j]-med;
	
	//luam pe rand toate perechiile de linii
	for(i=1;i<=nn;i++)
		for(j=i+lin-1;j-i<n && j<=nn;j++)
		{
			double c[mm+1]; //suma tuturor coloanelor intre cele 2 linii
			double d[mm+1]; //d[i]=suma maxima a unei secvente de lungime cel mult (m-c) ce se termina la poz i
			int e[mm+1],st,dr; //deq
			
			//construim c[]-ul
			for(c[0]=0,k=1;k<=mm;k++)
				c[k]=c[k-1]+b[j][k]-b[i-1][k];
			
			//facem deque-ul
			for(st=1,dr=0,k=1;k<=mm;k++)
			{
				while(st<=dr && c[e[dr]]>=c[k]) dr--;
				e[++dr]=k;
				while(st<=dr && k-e[st]>m-col) st++;
				d[k]=c[k]-c[e[st]];
			}
			
			//verificam toate secventele
			for(k=col;k<=(m<<1);k++)
				if(c[k]-c[k-col]+d[k-col] >= 0)
					return 1;
		}
	
	//daca am ajuns aici, inseamna ca media este prea mare
	return 0;
}

void solve()
{
	double mij,st=0,dr=vmax;
	//cautam binar media
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(verif(mij)) med=mij,st=mij+0.00000000001;
		else dr=mij-0.00000000001;
	}
}

void write()
{
	printf("%.3lf\n",med);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}