Cod sursa(job #2310209)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 30 decembrie 2018 20:07:08
Problema Elimin Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream cin("elimin.in");
ofstream cout("elimin.out");
short n,m,r,c,x;
int MaxSum;
bool elimin[10005];
vector<vector<short> > Mat;
vector<int> ColSum;
void bt(int k){

    if(k>r){

        /**for(int i=1;i<=n;i++)
            if(!elimin[i]){

                for(int j=1;j<=m;j++,cout<<' ')
                    cout<<Mat[i][j];

                cout<<'\n';

            }**/

        vector<int> SortColSum(ColSum);

        int SumTotal=0;

        sort(SortColSum.begin()+1,SortColSum.end());

        /**for(int i=1;i<=m;i++)
            cout<<ColSum[i]<<' ';

        cout<<"\n\n";**/

        for(int i=c+1;i<=m;i++)
            SumTotal+=SortColSum[i];

        MaxSum=max(MaxSum,SumTotal);

        SortColSum.clear();

        return ;

    }

    for(int i=1;i<=n;i++)
        if(!elimin[i]){

            elimin[i]=1;
            for(int j=1;j<=m;j++)
                ColSum[j]-=Mat[i][j];

            bt(k+1);

            elimin[i]=0;
            for(int j=1;j<=m;j++)
                ColSum[j]+=Mat[i][j];

        }

}

int main(){

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

    vector<short> V(m+1,0);
    ColSum.assign(m+1,0);

    Mat.push_back(V);

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            cin>>V[j];
            ColSum[j]+=V[j];

        }

        Mat.push_back(V);

    }

    V.clear();

    bt(1);

    cout<<MaxSum;

}