Cod sursa(job #7237)

Utilizator hadesgamesTache Alexandru hadesgames Data 21 ianuarie 2007 13:12:33
Problema Elimin Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 1.42 kb
#include <stdio.h>
long ln[7295],cl[7295];
int m,n;
int mincl()
{
	long min,p,i;
	min=2147483647;
	for (i=1;i<=n;i++)
		if (cl[i]<min)
		{
			min=cl[i];
			p=i;
		}
	return p;
}
int minln()
{
	long min,p,i;
	min=2147483647;
	for (i=1;i<=m;i++)
		if (ln[i]<min)
		{
			min=ln[i];
			p=i;
		}
	return p;
}

int main()
{
	int *a[87],c,r,i,j,aux;
	long s,x,y;
	FILE *in,*out;
	s=0;

	in=fopen("elimin.in","r");
	out=fopen("elimin.out","w");
	fscanf(in,"%d%d%d%d",&m,&n,&r,&c);
	i=1;
	x=0;
	for (i=1;i<=m;i++);
	{
		if (x==0)
		{
			i=1;
			x=1;
		}

		a[i]=new int[n];
	}
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			fscanf(in,"%d",&a[i][j]);
			ln[j]+=a[i][j];
			cl[j]+=a[i][j];
			s+=a[i][j];
		}
	while ((r>0)||(c>0))
	{
		if (r==0)
		{
			x=mincl();
			s-=cl[x];
			for (i=1;i<=m;i++)
				ln[i]-=a[i][x];
			cl[x]=2147483647;
			c--;
		}
		else
			if(c==0)
			{
				x=minln();
				s-=ln[x];
				for (i=1;i<=n;i++)
					cl[i]-=a[x][i];
				ln[x]=2147483647;
				r--;
			}
			else
			{
				x=minln();
				y=mincl();
				if (ln[x]<=cl[y])
				{
					s-=ln[x];
					for (i=1;i<=n;i++)
						cl[i]-=a[x][i];
					ln[x]=2147483647;
					r--;
				}
				else
				{
					x=y;
					s-=cl[x];
					for (i=1;i<=m;i++)
						ln[i]-=a[i][x];
					cl[x]=2147483647;
					c--;
				}
			}


	}
	fprintf(out,"%ld",s);
	fclose(out);
	fclose(in);



	return 0;
}