Cod sursa(job #2245344)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 25 septembrie 2018 09:36:31
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
using namespace std;

int n, m, r, c, t[7294][7294], sumaLin[7294], sumaCol[7294], sumaColP[7294], sumaMax, ln[7294];

void generareElim(int lin, int el){
	if (lin<n){
    if (r!=el){
			ln[el]=lin;
			generareElim(lin+1, el+1);
		}
		generareElim(lin+1, el);
	}
	else if (lin==n){
		if (el<r)
			return;
		else{
			int s=0, i, j, k;

			for (i=0; i<m; i++)
				sumaColP[i]=sumaCol[i];

			j=0;
			for (i=0; i<n; i++){
				if (i!=ln[j])
					s+=sumaLin[i];
				else{
					for (k=0; k<m; k++)
						sumaColP[k]-=t[i][k];
					if (j<r-1) j++;
				}
			}

			sort(sumaColP, sumaColP+m);

			for (k=0; k<c; k++)
				s-=sumaColP[k];

			if (s>sumaMax)
				sumaMax=s;
		}
	}
}

int main(){
	int i, j;
	bool invers=false;

	ifstream fin ("elimin.in");
	fin >> n >> m >> r >> c;
	if (n>m)
		invers=true;
	for (i=0; i<n; i++)
		for (j=0; j<m; j++){
			if (invers==false){
				fin >> t[i][j];
				sumaLin[i]+=t[i][j];
				sumaCol[j]+=t[i][j];
			}
			else{
				fin >> t[j][i];
				sumaLin[j]+=t[j][i];
				sumaCol[i]+=t[j][i];
			}
		}
	if (invers==true){
		swap(n, m);
		swap(r, c);
	}
	fin.close();

	ln[0]=n+1;
	generareElim(0, 0);

	ofstream fout ("elimin.out");
	fout << sumaMax;
	fout.close();

	return 0;
}