Pagini recente » Cod sursa (job #665856) | Cod sursa (job #2810356) | Cod sursa (job #2580966) | Cod sursa (job #951843) | Cod sursa (job #841271)
Cod sursa(job #841271)
#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;
}