Cod sursa(job #2765597)

Utilizator DragosC1Dragos DragosC1 Data 28 iulie 2021 13:34:48
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

int a[16][7295];
int n, m, R, C;

void read() {
    int i, j;
    ifstream f("elimin.in");
    f >> n >> m >> R >> C;
    if (n > m) {
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                f >> a[j][i];
        swap(n, m), swap(R, C);
    }
    else {
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
                f >> a[i][j];
    }
    f.close();
}

int Maxsum;
int comb[16];
bool elim[16];
int v[7295], l;

void solutie() {
    int i, sum = 0, j, aux;

    for (i = 1; i <= n; i++)
        elim[i] = 0;
    for (i = 1; i <= R; i++) 
        elim[comb[i]] = 1;
    
    for (i = 1; i <= n; i++)
        if (!elim[i])
            for (j = 1; j <= m; j++)
                sum += a[i][j];

    l = 0;
    for (j = 1; j <= m; j++) {
        aux = 0;
        for (i = 1; i <= n; i++)
            if (!elim[i])
                aux += a[i][j];
        v[++l] = aux;
    }

    sort(v + 1, v + l + 1);

    for (i = 1; i <= C; i++)
        sum -= v[i];
    if (sum > Maxsum)
        Maxsum = sum;
}

void back(int k) {
    for (int i = comb[k - 1] + 1; i <= n + k - R; i++) {
        comb[k] = i;
        if (k < R)
            back(k + 1);
        else solutie();
    }
}

void output() {
    ofstream g("elimin.out");
    g << Maxsum;
    g.close();
}

int main() {
    read();
    back(1);
    output();
    return 0;
}