Cod sursa(job #384324)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 19 ianuarie 2010 21:27:36
Problema Balans Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 2.97 kb
#include<stdio.h>
#define infile "balans.in"
#define outfile "balans.out"
#define nmax 313
#define zmax 1000
int a[nmax][nmax]; //matricea initiala
int b[nmax*nmax]; //toate elementele matricei
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
long long vmax; //suma celor mai mari lin*col elemente
long long vmin; //suma celor mai mici lin*col elemente
long long 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 unit(int st1, int dr1, int st2, int dr2)
{
	int c[dr1-st1+2],st3,dr3;
	for(st3=1,dr3=0;st1+dr3<=dr1;dr3++) c[dr3+1]=b[st1+dr3];
	while(st3<=dr3 && st2<=dr2)
	{
		if(c[st3]<=b[st2]) b[st1++]=c[st3++];
		else b[st1++]=b[st2++];
	}
	while(st3<=dr3) b[st1++]=c[st3++];
}

void msort(int st, int dr)
{
	int mij=(st+dr)>>1;
	if(st<mij) msort(st,mij);
	if(mij+1<dr) msort(mij+1,dr);
	unit(st,mij,mij+1,dr);
}

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;
	
	//inmultim matricea cu 10^nr_zecimale
	//pentru a nu mai lucra cu numere reale
	//si salvam in vectorul b[] toate numerele
	for(i=1;i<=nn;i++)
		for(j=1;j<=mm;j++)
			b[mm*(i-1)+j]=a[i][j]=a[i][j]*zmax;
	
	//sortam numerele din vector
	msort(1,nn*mm);
	
	//aflam vmin
	for(i=1;i<=lin*col;i++) vmin=vmin + (long long)b[i];
	
	//aflam vmax
	for(i=1;i<=lin*col;i++) vmax=vmax + (long long)b[nn*mm-i+1];
}

int verif(long long med)
{
	long long b[nn+1][mm+1]; //b[i][j]=b[1][j]+a[i][j]-med
	long long c[mm+1]; //suma tuturor coloanelor intre cele 2 linii
	long long 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
	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]+(long long)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++)
		{
			//construim c[]-ul
			//facem deque-ul
			//verificam secventele
			for(d[0]=c[0]=0,st=1,dr=0,k=1;k<=mm;k++)
			{
				c[k]=c[k-1]+b[j][k]-b[i-1][k];
				if(k<=mm-col)
				{
					while(st<=dr && c[e[dr]]>=c[k]) dr--;
					e[++dr]=k;
					if(k-e[st]>m-col) st++;
					d[k]=c[k]-c[e[st]];
				}
				if(k>=col && 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()
{
	long long mij,st=vmin/(lin*col),dr=vmax/(lin*col);
	//cautam binar media
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(verif(mij)) med=mij,st=mij+1;
		else dr=mij-1;
	}
}

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

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