Cod sursa(job #2310262)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 30 decembrie 2018 21:26:20
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 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<short> CurrIt;
void bt(int k){

    if(k>r){

        int SumTotal=0;
        vector<int> ColSum(m+1,0);

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

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

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

        MaxSum=max(MaxSum,SumTotal);

        ColSum.clear();

        return ;

    }

    for(CurrIt[k]=CurrIt[k-1]+1;CurrIt[k]<=n;CurrIt[k]++){

            elimin[CurrIt[k]]=1;
            bt(k+1);
            elimin[CurrIt[k]]=0;

        }

}

int main(){

    ios::sync_with_stdio(false);

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

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

    CurrIt.assign(n+1,0);

    Mat.push_back(V);

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

        for(int j=1;j<=m;j++)
            cin>>V[j];

        Mat.push_back(V);

    }

    if(r>c){

        vector<vector<short> > Trp;

        V.assign(n+1,0);

        Trp.push_back(V);

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

            for(int i=1;i<=n;i++)
                V[i]=Mat[i][j];

            Trp.push_back(V);

        }

        /**for(int i=1;i<=m;i++,cout<<'\n')
            for(int j=1;j<=n;j++,cout<<' ')
                cout<<Trp[i][j];**/

        Mat=Trp;
        swap(n,m);
        swap(r,c);

        Trp.clear();

    }

    V.clear();

    /**for(int i=1;i<=n;i++,cout<<'\n')
            for(int j=1;j<=m;j++,cout<<' ')
                cout<<Mat[i][j];**/
    bt(1);

    cout<<MaxSum;

}