Cod sursa(job #826962)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 1 decembrie 2012 14:40:52
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <vector>
#include <limits>
#include <algorithm>

inline void parsare(unsigned *psmax, unsigned short r,const std::vector<short> &ci,
                    const std::vector< std::vector<unsigned short> > &matrice);
inline bool inci(unsigned short i,const std::vector<short> &ci);

int main(){
    std::ifstream fin("elimin.in");
    std::ofstream fout("elimin.out");
    unsigned short m,n,r,c;
    fin>>m>>n>>r>>c;
    bool inv=false;
    if(m<n){inv=true; unsigned short temp=m; m=n; n=temp; temp=r; r=c; c=temp;}
    std::vector< std::vector<unsigned short> > matrice(n,std::vector<unsigned short>(m));
    if(inv)
        for(unsigned short ci=0;ci<n;ci++)
            for(unsigned short ri=0;ri<m;++ri)
                fin>>matrice[ci][ri];
    else
        for(unsigned short ri=0;ri<m;++ri)
            for(unsigned short ci=0;ci<n;ci++)
                fin>>matrice[ci][ri];
    //n,c
    unsigned smax=0;
    short i=0;
    std::vector<short> ci(c,-1);
    while(i>-1){
        if(ci[i]==n-c+i) ci[i--]=-1;
        else{
            if(i==0) ci[i]++;
            else if(ci[i]==-1) ci[i]=ci[i-1]+1;
            else ci[i]++;
            if(i==c-1) parsare(&smax,r,ci,matrice);
            else i++;
        }
    }
    fout<<smax<<'\n';
}
inline void parsare(unsigned *psmax, unsigned short r,const std::vector<short> &ci,
                    const std::vector< std::vector<unsigned short> > &matrice){
    std::vector<unsigned> rowssums(matrice[0].size(),0);
    for(unsigned short i=0;i<matrice.size();++i)
        if(!inci(i,ci))
            for(unsigned j=0;j<matrice[0].size();++j) rowssums[j]+=matrice[i][j];
    std::sort(rowssums.begin(),rowssums.end());
    unsigned totalrows=0;
    for(unsigned i=r;i<rowssums.size();++i) totalrows+=rowssums[i];
    if(totalrows>*psmax) *psmax=totalrows;
}
inline bool inci(unsigned short i,const std::vector<short> &ci){
    unsigned short c=0;
    while(c<ci.size()){
        if(i==ci[c]) return true;
        if(ci[c]>i) return false;
        c++;
    }
    return false;
}