Cod sursa(job #2310245)

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

    if(k>r){

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

        for(int i=1;i<=m;i++)
            ColSum[i]=MatSum[CurrIt[1]-1][i];

        for(int i=2;i<r;i++)
            for(int j=1;j<=m;j++)
                ColSum[j]+=MatSum[CurrIt[i]-1][j]-MatSum[CurrIt[i-1]][j];

        for(int i=1;i<=m;i++)
            ColSum[i]+=MatSum[n][i]-MatSum[CurrIt[r]][i];

        /**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(){

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

    vector<short> V(m+1,0);
    vector<int> Sum(m+1,0);
    CurrIt.assign(r+1,0);

    Mat.push_back(V);
    MatSum.push_back(Sum);

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

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

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

        }

        Mat.push_back(V);
        MatSum.push_back(Sum);

    }

    V.clear(); Sum.clear();

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

    if(r==0){

        sort(MatSum[n].begin()+1,MatSum[n].end());

        for(int i=c+1;i<=m;i++)
            MaxSum+=MatSum[n][i];

    }
    else bt(1);

    cout<<MaxSum;

}