Pagini recente » Cod sursa (job #3233852) | Cod sursa (job #1433030) | Cod sursa (job #2441236) | Cod sursa (job #3157541) | Cod sursa (job #827062)
Cod sursa(job #827062)
#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, bool flag);
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;
if(c==0) parsare(&smax,r,std::vector<short>(),matrice,false);
if(c==n || r==m ) smax=0;
else{
bool reverse=false;
if(c>(n/2)){ reverse=true; c = n-c; }
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,reverse);
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, bool flag){
std::vector<unsigned> rowssums(matrice[0].size(),0);
for(unsigned short i=0;i<matrice.size();++i)
if(flag==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){ //based on binary search
unsigned short pos=0, step;
for(step=1;step<ci.size();step<<=1);
step>>=1;
for(;step;step>>=1){
if(((pos|step)<ci.size())&&(ci[pos|step]<=i)) pos|=step;
}
if(ci[pos]==i) return true;
else return false;
}