Cod sursa(job #2295865)

Utilizator TooHappyMarchitan Teodor TooHappy Data 3 decembrie 2018 23:44:19
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
 
using namespace std;

ifstream in("elimin.in");
ofstream out("elimin.out");

int m, n, r, c, table[1050][1050], ans = -1e9, minn, maxx, minnTarget, maxxTarget;
int sol[20];

void solve() {
    vector< int > sums;

    for(int i = 1; i <= maxx; ++i) {
        int tempSum = 0;

        for(int j = 1; j <= minn; ++j) {
            if(!sol[j]) {
                tempSum += table[i][j];
            }
        }

        sums.push_back(tempSum);
    }
    sort(sums.begin(), sums.end());

    int currSum = 0;
    for(int i = maxxTarget; i < maxx; ++i) {
        currSum += sums[i];
    }

    ans = max(ans, currSum);
}

void bkt(int k) {
    if(k == minn + 1) {
        int cnt = 0;
        for(int i = 1; i <= k; ++i) {
            if(sol[i] != 0) {
                cnt++;
            }
        }

        if(cnt == minnTarget) {
            solve();   
        }
    } else {
        for(int i = 0; i <= 1; ++i) {
            sol[k] = i;
            bkt(k + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    in >> m >> n >> r >> c;
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            in >> table[i][j];
        }
    }

    if(m < n) {
        minn = m; maxx = n;
        minnTarget = r; maxxTarget = c;

        for(int i = 1; i <= m; ++i) {
            for(int j = i + 1; j <= n; ++j) {
                swap(table[i][j], table[j][i]);
            }
        }
    } else {
        minn = n; maxx = m;
        minnTarget = c; maxxTarget = r;
    }

    bkt(1);

    out << ans << "\n";

    in.close(); out.close();
 
    return 0;
}