Cod sursa(job #841271)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 23 decembrie 2012 22:49:49
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <fstream>
#include <vector>
#include <algorithm>

typedef unsigned short USH;
inline unsigned GetSum(USH C,USH M,USH N, const std::vector< std::vector<USH> > &matr,
                       const std::vector<short> &x, unsigned tSum, bool inv);

int main(){
    std::ifstream fin("elimin.in");
    std::ofstream fout("elimin.out");
    USH M,N,R,C;
    unsigned maxSum=0;
    std::vector < std::vector<USH> > matr(M<N?M:N,std::vector<USH>(M>N?M:N));
    //citire...
    fin>>M>>N>>R>>C;
    if(M<N)
        for(USH i=0; i<M; ++i)
            for(USH j=0; j<N; ++j) fin>>matr[i][j];
    else{
        for(USH i=0; i<M; ++i)
            for(USH j=0; j<N; ++j) fin>>matr[j][i];
        USH temp;
        temp=C; C=R; R=temp;
        temp=M; M=N; N=temp;
    }

    //precalc....
    unsigned totalSum=0;
    for(USH i=0; i<M; ++i)
            for(USH j=0; j<N; ++j) totalSum+=matr[i][j];
    std::vector<unsigned> colSums(N,0);
    std::vector<unsigned> rowSums(M,0);
    for(USH i=0; i<M; ++i)
        for(USH j=0; j<N; ++j){ rowSums[i]+=matr[i][j]; colSums[j]+=matr[i][j]; }

    //start...
    if(R==M||C==N) maxSum=0;
    else if(R==0&&C==0) maxSum=totalSum;
    else if(R==0){
        maxSum=0;
        std::sort(colSums.begin(),colSums.end());
        for(USH i=C;i<N;++i) maxSum+=colSums[i];
    }
    else if(C==0){
        maxSum=0;
        std::sort(rowSums.begin(),rowSums.end());
        for(USH i=R;i<M;++i) maxSum+=rowSums[i];
    }
    else{
        bool inv=false;
        if(R>M/2){ R=M-R; inv=true; }

        short k=0;
        std::vector<short> x(R,-1);
        while(k>-1){
            if(k==0) x[k]++;
            else if(x[k]==-1) x[k]=x[k-1]+1;
            else x[k]++;

            if(x[k]>M-R+k) x[k--]=-1;
            else if(k==R-1){
                unsigned cs=GetSum(C,M,N,matr,x,totalSum,inv);
                if(cs>maxSum) maxSum=cs;
            }
            else ++k;
        }
    }
    fout<<maxSum<<'\n';
}

inline unsigned GetSum(USH C,USH M,USH N, const std::vector<std::vector<USH> > &matr,const std::vector<short> &x,unsigned tSum,bool inv){
    std::vector<unsigned> ccolsum(N,0);
    if(!inv){
        USH c=0;
        for(USH i=0;i<M;++i)
            if(c<x.size())
                if(!x[c]==i) for(USH j=0;j<N;++j) ccolsum[j]+=matr[i][j];
                else c++;
            else for(USH j=0;j<N;++j) ccolsum[j]+=matr[i][j];
    }
    else for(USH i=0;i<x.size();++i) for(USH j=0;j<N;++j) ccolsum[j]+=matr[x[i]][j];
    std::sort(ccolsum.begin(),ccolsum.end());
    unsigned ret=0;
    for(USH i=C;i<N;++i) ret+=ccolsum[i];
    return ret;
}