Cod sursa(job #976699)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 23 iulie 2013 18:42:17
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

inline void back_row(unsigned &max, unsigned m, unsigned n, unsigned r, unsigned c,
                     const vector<unsigned> &matr);
inline void back_col(unsigned &max, unsigned m, unsigned n, unsigned r, unsigned c,
                     const vector<unsigned> &matr);

bool grt_comb(unsigned n1,unsigned k1,unsigned n2,unsigned k2){
    if(k1>(n1/2)) k1=n1-k1;
    if(k2>(n2/2)) k2=n2-k2;
    unsigned long long C1=1,C2=1;
    for(unsigned i=n1-k1+1;i<=n1;++i) C1*=i;
    for(unsigned i=n2-k2+1;i<=n2;++i) C2*=i;
    C1/=k1;
    C2/=k2;
    return C1>C2;
}

int main(){
    ifstream fin("elimin.in");
    ofstream fout("elimin.out");

    unsigned m,n,r,c;
    fin>>m>>n>>r>>c;

    vector<unsigned> matr(m*n);
    for(unsigned i=0;i<m*n;++i) fin>>matr[i];

    unsigned max=0;

    if(c==0){
        vector<unsigned> sums(m,0);
        for(unsigned i=0;i<m;++i){
            for(unsigned j=0;j<n;++j){
                sums[i]+=matr[m*i+j];
            }
        }
        sort(sums.begin(),sums.end());
        for(unsigned i=r;i<m;++i) max+=sums[i];
    }

    else if(r==0){
        vector<unsigned> sums(n,0);
        for(unsigned i=0;i<m;++i){
            for(unsigned j=0;j<n;++j) sums[j]+=matr[m*i+j];
        }
        sort(sums.begin(),sums.end());
        for(unsigned i=c;i<n;++i) max+=sums[i];
    }

    else if(grt_comb(n,c,m,r)) back_row(max,m,n,r,c,matr);
    else back_col(max,m,n,r,c,matr);

    fout<<max<<'\n';
    return 0;
}

inline void back_row(unsigned &max, unsigned m, unsigned n, unsigned r, unsigned c,
                     const vector<unsigned> &matr){
    vector<unsigned> selected(r,m);
    int k=0;
    while(k>-1){
        //update
        if(k==0) if(selected[0]==m) selected[0]=0;
                 else selected[0]++;
        else if(selected[k]==m) selected[k]=selected[k-1]+1;
        else selected[k]++;
        //test
        if(selected[k]>m-r+k){selected[k]=m; k--;}
        else if(k==r-1){
            unsigned curr_max=0;

            //colselect
            vector<unsigned> sums(n,0);
            unsigned cc=0;
            for(unsigned i=0;i<m;++i){
                if(cc<r&&selected[cc]==i) ++cc;
                else for(unsigned j=0;j<n;++j) sums[j]+=matr[m*i+j];
            }
            sort(sums.begin(),sums.end());
            for(unsigned i=c;i<n;++i) curr_max+=sums[i];

            if(curr_max>max) max=curr_max;
        }
        else ++k;
    }
}
inline void back_col(unsigned &max, unsigned m, unsigned n, unsigned r, unsigned c,
                     const vector<unsigned> &matr){
    vector<unsigned> selected(c,n);
    int k=0;
    while(k>-1){
        //update
        if(k==0) if(selected[0]==n) selected[0]=0;
                 else selected[0]++;
        else if(selected[k]==n) selected[k]=selected[k-1]+1;
        else selected[k]++;
        //test
        if(selected[k]>n-c+k){selected[k]=n; k--;}
        else if(k==c-1){
            unsigned curr_max=0;
            //rowselect
            vector<unsigned> sums(m,0);
            for(unsigned i=0;i<m;++i){
                unsigned cc=0;
                for(unsigned j=0;j<n;++j){
                    if(cc<c&&selected[cc]==j) ++cc;
                    else sums[i]+=matr[m*i+j];
                }
            }
            sort(sums.begin(),sums.end());
            for(unsigned i=r;i<m;++i) curr_max+=sums[i];

            if(curr_max>max) max=curr_max;
        }
        else ++k;
    }
}