Pagini recente » Cod sursa (job #617793) | Cod sursa (job #1001205) | Cod sursa (job #635410) | Cod sursa (job #2469981) | Cod sursa (job #1015336)
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#define NMAX 700
using namespace std;
int n, m, r, c;
int a[NMAX][NMAX];
int v[NMAX];
int maxim = 0;
bitset<7295> 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;
}