Pagini recente » Cod sursa (job #1110452) | Cod sursa (job #2476922) | Cod sursa (job #1273381) | Cod sursa (job #3181486) | Cod sursa (job #1014810)
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#define NMAX 70
using namespace std;
int n, m, r, c;
int a[NMAX][NMAX];
int v[NMAX];
int maxim = 0;
bitset<NMAX> 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;
}
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 = 1 + 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;
}