Cod sursa(job #1893765)

Utilizator tudortarniceruTudor Tarniceru tudortarniceru Data 25 februarie 2017 23:51:46
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

const int MAXN = 7300;
int n, m;
int r, c;
int v[MAXN][MAXN];

int srt(int a, int b) {
    return a > b;
}

int main() {

    fin >> n >> m >> r >> c;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (n > m) {
                fin >> v[j][i];
            }
            else {
                fin >> v[i][j];
            }
        }
    }
    if (n > m) {
        swap(n, m);
        swap(r, c);
    }
    int sol = 0;
    int l = (1 << n);
    for (int i = 0; i < l; ++i) {
        int k = 0;
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                k++;
            }
        }
        if (k == n - r) {
            int a[MAXN];
            for (int j = 1; j <= m; ++j) {
                a[j] = 0;
                for (int k = 1; k <= n; ++k) {
                    if (i & (1 << (k - 1))) {
                        a[j] += v[k][j];
                    }
                }
            }
            sort(a + 1, a + m + 1, srt);
            int s = 0;
            for (int k = 1; k <= m - c; ++k) {
                s += a[k];
            }
            sol = max(sol, s);
        }
    }
    fout << sol;

    fout.close();
    return 0;
}