Cod sursa(job #2398650)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 5 aprilie 2019 20:07:57
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int n, m, r, c;
int table[600][600];
int minsum = 0;
vector<int>sumeL;

int countZeros(int x){
    int i;
    for (i = 0; x; ++i) {
        x-=(x & (-x));
    }
    return i;
}

void backTrack(){

    int goTo = (1 << n);
    for (int i = 0; i < goTo; ++i) {
        int copie = i;
        if(countZeros(i) == r){
            for(int j = 0; j < m; j++)
                sumeL.push_back(0);
            int sum = 0;
            for(int j = n - 1; j >= 0; --j, copie = (copie >> 1)){
                if((copie & 1) == 0){
                   for(int k = 0; k < m; ++k){
                       sumeL[k] += table[k][j];
                       sum += table[k][j];
                   }
                }
            }
            sort(sumeL.begin(), sumeL.end());
            for (int l = 0; l < c; ++l) {
                sum-=sumeL[l];
            }
            sumeL.clear();
            if(sum > minsum)
                minsum = sum;
        }
    }
}

int main() {
    f>>n>>m>>r>>c;
    bool ok = false;
    if(m < n){
        swap(m, n);
        swap(r, c);
        ok = true;
    }
    for(int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j) {
            if(ok){
                f>>table[j][i];
            }
            else{
                f>>table[i][j];
            }
        }
    }
    backTrack();
    g<<minsum;
    return 0;
}