Cod sursa(job #2295839)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 3 decembrie 2018 23:09:04
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("elimin.in");
ofstream fout("elimin.out");
 
int n, m, r, c, totalSum;
vector < vector < int > > v;
vector < bool > viz;
vector < int > tmp, DP;

int ans = INT_MIN;
void Back(int lvl, int picked) {
    if (picked == r) {
        tmp.assign(m, 0);
        int sum = totalSum;
        for (int i = 0; i < n; ++i) {
            if (viz[i]) {
                sum -= DP[i];
                continue;
            }
            for (int j = 0; j < m; ++j) {
                tmp[j] += v[i][j];
            }
        }

        sort(tmp.begin(), tmp.end());
        for (int i = 0; i < c; ++i) {
            sum -= tmp[i];
        }
        ans = max(ans, sum);
        return;
    }
    if (lvl >= n) return;

    viz[lvl] = false;
    Back(lvl + 1, picked);
    viz[lvl] = true;
    Back(lvl + 1, picked + 1);
    viz[lvl] = false;
}

int main() {
    ios::sync_with_stdio(false);

    fin >> n >> m >> r >> c;

    if (m < n) {
        swap(r, c);
        swap(n, m);
        v.resize(n);
        for (auto &it: v) it.resize(m);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                fin >> v[j][i];
            }
        }
    } else {
        v.resize(n);
        for (auto &it: v) it.resize(m);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                fin >> v[i][j];
            }
        }
    }

    DP.resize(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            totalSum += v[i][j];
            DP[i] += v[i][j];
        }
    }
    
    tmp.resize(m);
    viz.resize(n);
    Back(0, 0);
    fout << ans;
    return 0;
}