Pagini recente » Cod sursa (job #2263240) | Cod sursa (job #1470306) | Cod sursa (job #163585) | Cod sursa (job #1517835) | Cod sursa (job #2296175)
#include <bits/stdc++.h>
using namespace std;
ifstream in("elimin.in");
ofstream out("elimin.out");
int m, n, r, c, ans = -1e9, minn, maxx, minnTarget, maxxTarget, allSum;
vector< int > precalc, sums, sol(20, 0);
vector< vector< int > > table;
void solve() {
int sum = allSum;
for(int j = 0; j <= maxx; ++j) {
sums[j] = 0;
}
for(int i = 1; i <= minn; ++i) {
if(!sol[i]) {
for(int j = 1; j <= maxx; ++j) {
sums[j] += table[i][j];
}
} else {
sum -= precalc[i];
}
}
sort(sums.begin(), sums.end());
for(int j = 1; j <= maxxTarget; ++j) {
sum -= sums[j];
}
ans = max(ans, sum);
}
void bkt(int k, int deleted) {
if(k > minn + 1) {
return;
}
if(deleted == minnTarget) {
solve();
} else {
for(int i = 0; i <= 1; ++i) {
sol[k] = i;
bkt(k + 1, deleted + (i == 1));
}
sol[k] = 0;
}
}
int main() {
ios::sync_with_stdio(false); in.tie(0); out.tie(0);
in >> m >> n >> r >> c;
if(m < n) {
minn = m; maxx = n;
minnTarget = r; maxxTarget = c;
table.resize(m + 1, vector< int > (n + 1)); precalc.resize(minn + 1); sums.resize(maxx + 1);
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
in >> table[i][j];
}
}
} else {
minn = n; maxx = m;
minnTarget = c; maxxTarget = r;
table.resize(n + 1, vector< int > (m + 1)); precalc.resize(minn + 1); sums.resize(maxx + 1);
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
in >> table[j][i];
}
}
}
for(int i = 1; i <= minn; ++i) {
for(int j = 1; j <= maxx; ++j) {
precalc[i] += table[i][j];
allSum += table[i][j];
}
}
bkt(1, 0);
out << ans << "\n";
in.close(); out.close();
return 0;
}