Pagini recente » Cod sursa (job #1867399) | Cod sursa (job #1235004) | Cod sursa (job #408278) | Cod sursa (job #2565369) | Cod sursa (job #2245370)
#include <algorithm>
#include <cstdio>
#include <fstream>
int a[2 + 20][2 + 8200], sol = 0, sumCol[2 + 8200];
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;
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]);
else
scanf("%d", &a[i][j]);
if (swapping) {
std::swap(n, m);
std::swap(r, c);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sumCol[j] += a[i][j];
backt(n, m, r, c, 1, 0);
printf("%d", sol);
return 0;
}