Pagini recente » Cod sursa (job #1076194) | Cod sursa (job #2520365) | Cod sursa (job #2520016) | Cod sursa (job #2114419) | Cod sursa (job #1015346)
#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;
char elim[7295];
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 < m; i++) {
if (elim[i]) continue;
for (int j = 0; j < n; j++) {
v[j] += a[j][i];
}
}
} else {
for (int i = 0; i < n; i++) {
if (elim[i]) continue;
for (int j = 0; j < m; j++) {
v[j] += a[i][j];
}
}
}
sort(v, v + dim_v);
int suma = 0;
for (int j = celalalt; j < dim_v; j++) {
suma += v[j];
v[j] = 0;
}
if (suma > maxim) maxim = suma;
}
void backtracking(int k, int last) {
if (k > dim) {
solutie();
return;
}
for (int i = last + 1; i < dim_e - (dim - k); i++) {
elim[i] = 1;
backtracking(k + 1, i);
elim[i] = 0;
}
}
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, -1);
ofstream out("elimin.out");
out<<maxim<<"\n";
return 0;
}