Cod sursa(job #665004)

Utilizator suzanicaSuzanica Mihu suzanica Data 21 ianuarie 2012 13:16:23
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<fstream>
#define dmax 1000
#include<algorithm>
using namespace std;

int n,m,l,c;
int a[dmax][dmax];
long long s[dmax],sc[dmax],scc[dmax]; 
/*s este vectorul cu configuratiile de elimnari generate de bkt;
  sc este vectorul cu sumele pe coloanele matricii initiale
  scc este vectorul cu sumele pe coloanele matricii cu randurile eliminat*/
long long summax;

void citire()
{
 int i,j;
	
 ifstream fin("elimin.in");
 
 fin>>n>>m>>l>>c;
 
 if (n > m)
	 {
	  for (i=1; i<=n; i++)
		  for (j=1; j<=m; j++)
			  {
			   fin>>a[j][i];
			   sc[i] += a[j][i];
			  }
	 
	  swap(n,m); 
	  swap(l,c);
	 } else
	 for (i=1; i<=n; i++)
		 for (j=1; j<=m; j++)
			 {
			  fin>>a[i][j];
			  sc[j] += a[i][j];
			 }
	
 fin.close();
}


void solve()
{
 int i,j;
 long long sum=0;
	
 for (i=1; i<=m; i++)
	 scc[i] = sc[i];
	
 for (i=1; i<=l; i++)
	 for (j=1; j<=m; j++)
		 scc[j] -= a[s[i]][j];

 sort(scc+1, scc+m+1);
 
 for (i=c+1; i<=m; i++)
	 sum += scc[i];
 
 summax = max(summax, sum);
}


void bkt(int k)
{
 int i;
	
 if (k == l+1) /*daca am o configuratie completa*/
	 solve(); else
	 for (i=s[k-1]+1; i<=n; i++)
		 {
		  s[k] = i;
		  bkt(k+1);
		 }	
}


void afisare()
{
 ofstream fout("elimin.out");
 
 fout<<summax;
 
 fout.close();
}


int main()
{
	
 citire();
 bkt(1);
 afisare();
	
 return 0;
}