Cod sursa(job #1014337)

Utilizator IoannaPandele Ioana Ioanna Data 22 octombrie 2013 15:50:26
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>

using namespace std;
int n, m, r, c;
int a[700][700];
int v[700];
int maxim = 0;
bitset<700> elim;
vector<int> st;

bool swapb = false;
int dim, celalalt, dim_v;

void read() {
	ifstream in ("elimin.in");
	in>>n>>m>>r>>c;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
		 	in >> a[i][j];
		}
}

void solutie() {
	if (swapb)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (elim[j]) continue;
				v[i] += a[i][j];
			}
	else 
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++) {
				if (elim[j]) continue;
				v[i] += a[j][i];
			}
	sort(v, v + dim_v);
	int suma = 0;
	for (int j = celalalt; j < dim_v; j++)
		suma += v[j];
	if (suma > maxim) maxim = suma;

}

void backtracking(int k) {
	if (k > dim) {
		solutie();
		return;
	}

	for (int i = st[k - 1]; i < dim; i++) {
		st.push_back(i); 
		elim[i] = true;
	  backtracking(k + 1);
	  elim[i] = false;
	  st.pop_back();
  }


}

int main() {
	read();
	if (n > m) {
		dim = c;
		dim_v = n;
		celalalt = r;
		swapb = true;
	} else {
		dim = r;
		dim_v = m;
		celalalt = c;
	}
	st.push_back(-1);
	backtracking(1);
	ofstream out("elimin.out");
	out<<maxim<<"\n";
	return 0;
}