Cod sursa(job #48227)

Utilizator biskisDudas Daniel biskis Data 4 aprilie 2007 15:09:31
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<fstream.h>
#include<limits.h>
int b[100][100],d[100][100];
main()
{ifstream f("elimin.in");
ofstream g("elimin.out");
int n,m,r,c,i,j,tot=0,a[100][100];
f>>n>>m>>r>>c;
for(i=0;i<n;i++)
	for(j=0;j<m;j++)
		{f>>a[i][j];
		if(a[i][j]!=0)
			{int ii;
			tot+=a[i][j];
			for(ii=0;ii<=m;ii++)
				b[i][ii]+=a[i][j];
			for(ii=0;ii<=n;ii++)
				d[ii][j]+=a[i][j];
			}
		}
int pozi,pozj,min;

while(r>0 && c>0)
	{min=INT_MAX;
	for(int iii=0;iii<n;iii++)
		for(int jjj=0;jjj<m;jjj++)
			if(b[iii][jjj]+d[iii][jjj]-a[iii][jjj]<min)
				{min=b[iii][jjj]+d[iii][jjj]-a[iii][jjj];
				pozi=iii;
				pozj=jjj;
				}
	tot-=min;
	for(i=0;i<=n;i++)
		for(j=0;j<m;j++)
			{b[i][j]-=a[i][pozj];
			d[i][j]-=a[pozi][j];
			}
	for(i=0;i<n;i++)
		d[i][pozj]=INT_MAX;
	for(j=0;j<m;j++)
		b[pozi][j]=INT_MAX;
	r--;
	c--;
	}
while(r>0 && c>0)
	{min=INT_MAX;
	for(int iii=0;iii<n;iii++)
		for(int jjj=0;jjj<m;jjj++)
			if(d[iii][jjj]<min)
				{min=d[iii][jjj];
				pozi=iii;
				pozj=jjj;
				}
	tot-=min;
	for(i=0;i<=n;i++)
		for(j=0;j<m;j++)
			d[i][j]-=a[pozi][j];
	for(i=0;i<n;i++)
		d[i][pozj]=INT_MAX;
	c--;
	}
while(r>0)
	{min=INT_MAX;
	for(int iii=0;iii<n;iii++)
		for(int jjj=0;jjj<m;jjj++)
			if(b[iii][jjj]<min)
				{min=b[iii][jjj];
				pozi=iii;
				pozj=jjj;
				}
	tot-=min;
	for(i=0;i<=n;i++)
		for(j=0;j<m;j++)
			{b[i][j]-=a[i][pozj];
			}
	for(j=0;j<m;j++)
		b[pozi][j]=INT_MAX;
	r--;
	}
g<<tot;
g.close();
f.close();
}