Cod sursa(job #976375)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 23 iulie 2013 08:56:09
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.02 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

inline unsigned colselect(const vector<unsigned short> &selected,
                          unsigned short m, unsigned short n, unsigned short r, unsigned short c,
                          const vector< vector<unsigned short> > &matr);
inline unsigned rowselect(const vector<unsigned short> &selected,
                          unsigned short m, unsigned short n, unsigned short r, unsigned short c,
                          const vector< vector<unsigned short> > &matr);

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) max=rowselect(vector<unsigned short>(0),m,n,r,c,matr);
    else if(r==0) max=colselect(vector<unsigned short>(0),m,n,r,c,matr);
    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=colselect(selected,m,n,r,c,matr);
            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=rowselect(selected,m,n,r,c,matr);
            if(curr_max>max) max=curr_max;
        }
        else ++k;
    }
}

inline unsigned colselect(const vector<unsigned short> &selected,
                          unsigned short m, unsigned short n, unsigned short r, unsigned short c,
                          const vector< vector<unsigned short> > &matr){
    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];
    }
    sort(sums.begin(),sums.end());
    unsigned ret=0;
    for(unsigned short i=c;i<n;++i) ret+=sums[i];
    return ret;
}
inline unsigned rowselect(const vector<unsigned short> &selected,
                          unsigned short m, unsigned short n, unsigned short r, unsigned short c,
                          const vector< vector<unsigned short> > &matr){
    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];
        }
    }
    sort(sums.begin(),sums.end());
    unsigned ret=0;
    for(unsigned short i=r;i<m;++i) ret+=sums[i];
    return ret;
}