Cod sursa(job #976715)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 23 iulie 2013 19:14:34
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.63 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

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

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

    unsigned max=0;

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

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

    else if(n>m) 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 short m, unsigned short n, unsigned short r, unsigned short c,
                     const vector< vector<unsigned short> > &matr){
    vector<unsigned short> 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 short cc=0;
            for(unsigned short i=0;i<m;++i){
                if(cc<r&&selected[cc]==i) ++cc;
                else for(unsigned short j=0;j<n;++j) sums[j]+=matr[i][j];
            }
            nth_element(sums.begin(),sums.begin()+c,sums.end());
            for(unsigned short 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 short m, unsigned short n, unsigned short r, unsigned short c,
                     const vector< vector<unsigned short> > &matr){
    vector<unsigned short> 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 short i=0;i<m;++i){
                unsigned short cc=0;
                for(unsigned short j=0;j<n;++j){
                    if(cc<c&&selected[cc]==j) ++cc;
                    else sums[i]+=matr[i][j];
                }
            }
            nth_element(sums.begin(),sums.begin()+r,sums.end());
            for(unsigned short i=r;i<m;++i) curr_max+=sums[i];

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