Cod sursa(job #422730)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 23 martie 2010 09:49:41
Problema Balans Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
# include <stdio.h>
# include <math.h>

# define MAXN 150

unsigned long int a[2*MAXN+1][2*MAXN+1],sum[2*MAXN+1][2*MAXN+1];
long int n,m,r,c,elemmaxim;

void citire()
{
	FILE *f=fopen("balans.in","r");
	fscanf(f,"%ld%ld%ld%ld",&n,&m,&r,&c);
	long int i,j;
	long int aux;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			{
			fscanf(f,"%ld",&aux);
			if (aux>elemmaxim)
				elemmaxim=aux;
			a[i][j]=aux;
			a[i+n][j]=a[i][j];
			a[i][j+m]=a[i][j];
			a[i+n][j+m]=a[i][j];
			}
	fclose(f);
	for (i=1;i<=2*n;i++)
		for (j=1;j<=2*m;j++)
			sum[i][j]=sum[i-1][j]+a[i][j];
}

void scrie(float sol)
{
	FILE *g=fopen("balans.out","w");
	fprintf(g,"%.3f\n",sol);
	fclose(g);
}

float sc[2*MAXN+1];
float sumsc[2*MAXN+1];
long int deq[2*MAXN+1];

long int existsPositiveSubsequence()
{
	long int begin=1,end=0,j;
	for (j=c;j<=2*m;j++)
		{
		//adauga la deq j-c
		deq[++end]=j-c;
		//scufunda-l in deq
		while (end-1>=begin && sumsc[deq[end]]<sumsc[deq[end-1]])
			{
			deq[end-1]=deq[end];
			end--;
			}
		//adu capatul deq-ului la curent
		while (j-deq[begin]>m) 
			begin++;
		//verifica daca noua suma este pozitiva
		if (sumsc[j]-sumsc[deq[begin]] > 0)
			return 1;
		}
	return 0;
}

long int canBeObtained(float avg)
{

//	printf("Now testing average: %.3f\n",avg);

	//ne alegem doua linii si calculam sumele pe coloane
	long int lineup, linedown, j;
	for (linedown = r; linedown <= 2*n; linedown ++)
		for (lineup = n < linedown-r? n : linedown-r; lineup >= 0; --lineup)
			{
			for (j=1;j<=2*m;j++)
				{
				sc[j]=sum[linedown][j]-sum[lineup][j]-avg*(linedown-lineup);
				sumsc[j]=sc[j]+sumsc[j-1];
				}

//			for (j=1;j<=2*m;j++)			
//				printf("%.3f ",sc[j]);
//			printf("\n");

			if (existsPositiveSubsequence())
				return 1;
			}
	return 0;
}

float calculeaza(float li, float lf)
{
	float m;
	while ( (li-lf>=0? li-lf: lf-li) > 1e-3 )
		{
		m =(li+lf)/2;
		//daca m este o medie care se poate obtine, atunci cauta una mai mare
		if (canBeObtained(m)) li=m;
		else lf=m;
		}
	return li;
}

int main()
{
	citire();
	float sol = calculeaza(0,elemmaxim);
	scrie(sol);
	return 0;
}