Cod sursa(job #1015331)

Utilizator IoannaPandele Ioana Ioanna Data 24 octombrie 2013 13:44:22
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#define NMAX 7000

using namespace std;

int n, m, r, c;
int a[NMAX][17];
int v[NMAX];
int maxim = 0;
bitset<NMAX> elim;

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

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++) {
            v[i] = 0;
			for (int j = 0; j < m; j++) {
				if (elim[j]) continue;
                v[i] += a[i][j];
			}
		}
	 } else {
		for (int i = 0; i < m; i++) {
            v[i] = 0;
			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, int last) {
	if (k > dim) {
		solutie();
		return;
	}

	for (int i = last + 1; i < dim_e; i++) {
        elim[i] = true;
        backtracking(k + 1, i);
        elim[i] = false;
  }
}

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