Pagini recente » Cod sursa (job #728560) | Cod sursa (job #801574) | Cod sursa (job #225258) | Cod sursa (job #3003658) | Cod sursa (job #2245365)
#include <algorithm>
#include <cstdio>
#include <fstream>
int a[2 + 20][2 + 8200], sol = 0, sumCol[2 + 20];
bool selected[2 + 20];
void backt(int n, int m, int r, int c, int k, int prev) {
if (k > r) {
int copy[2 + m];
for (int j = 1; j <= m; j++)
copy[j] = sumCol[j];
std::sort(copy + 1, copy + m + 1);
int sum = 0;
for (int j = c + 1; j <= m; j++)
sum += copy[j];
sol = std::max(sum, sol);
} else
for (int i = prev + 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
sumCol[j] -= a[i][j];
backt(n, m, r, c, k + 1, i);
for (int j = 1; j <= m; j++)
sumCol[j] += a[i][j];
}
}
int main() {
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
int n, m, r, c;
scanf("%d%d%d%d", &n, &m, &r, &c);
bool swapping = false;
int sumAll = 0;
if (m < n)
swapping = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (swapping) {
scanf("%d", &a[j][i]);
sumAll += a[j][i];
sumCol[i] += a[j][i];
} else {
scanf("%d", &a[i][j]);
sumAll += a[i][j];
sumCol[j] += a[i][j];
}
if (swapping) {
std::swap(n, m);
std::swap(r, c);
}
backt(n, m, r, c, 1, 0);
printf("%d", sol);
return 0;
}