Cod sursa(job #2296175)

Utilizator TooHappyMarchitan Teodor TooHappy Data 4 decembrie 2018 15:57:18
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#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;
}