Cod sursa(job #2307115)

Utilizator LucianTLucian Trepteanu LucianT Data 23 decembrie 2018 19:14:06
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int maxN=8e3+1;
const int maxMin=17;

int countBits(int n){
    int res=0;

    while(n){
        n=n&(n-1);
        res++;
    }

    return res;
}

int n,m,r,c;
int a[maxMin][maxN];

int sum[maxN];
int sol;

int main(){
    ifstream cin("elimin.in");
    ofstream cout("elimin.out");

    cin>>n>>m>>r>>c;

    if(n<=m){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>a[i][j];
            }
        }
    } else {
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>a[j][i]; //rip cache
            }
        }
        swap(n,m);
        swap(r,c);
    }

    int lim=(1<<n);
    for(int mask=0;mask<lim;mask++){
        if(countBits(mask)==r){

            for(int i=0;i<m;i++)
                sum[i]=0;

            for(int i=0;i<n;i++)
                if((mask&(1<<i))==0)
                    for(int j=0;j<m;j++)
                        sum[j]+=a[i][j];

            sort(sum,sum+m);
            int currentSum=0;

            for(int i=c;i<m;i++){
                currentSum+=sum[i];
            }

            sol=max(sol,currentSum);
        }
    }

    cout<<sol;

    return 0;
}