Pagini recente » Cod sursa (job #2144644) | Cod sursa (job #2676712) | Cod sursa (job #312626) | Cod sursa (job #1444715) | Cod sursa (job #2512343)
#include <fstream>
#include <algorithm>
#define lim 600
using namespace std;
ifstream cin("elimin.in");
ofstream cout("elimin.out");
int n,m;
int sl[lim],sc[lim],r,cc,ult[lim],ans=-32000*86,nv[lim],st,c[lim][lim];
void backt(int lvl)
{
if(lvl==r)
{
for (int i=1;i<=m;++i)
nv[i]=sc[i];
sort(nv+1,nv+m+1);
int s=0;
for(int i=m;i>cc;--i)
s+=nv[i];
ans=max(ans,s);
}
else
{ for(int j=ult[lvl]+1;j<=n;++j){
for(int i=1;i<=m;++i)
sc[i]-=c[j][i];
ult[lvl+1]=j;
backt(lvl+1);
for(int i=1;i<=m;++i)
sc[i]+=c[j][i];
}
}
}
int main()
{
int i,j,mat;
cin>>n>>m>>r>>cc;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{ cin>>mat;
st+=mat;
c[i][j]=mat;
// sl[i]+=mat;
// sc[j]+=mat;
}
if(n>m)
{
for(i=1;i<=n;++i)
for(j=1;j<i;++j){
swap(c[i][j],c[j][i]);
// sc[i]+=c[n-j+1][i];
// sl[n-j+1]+=c[n-j+1][i];
}
swap(n,m);
swap(r,cc);
for(i=1;i<=n;++i){
for(j=1;j<=m;++j)
sc[j]+=c[i][j],sl[i]+=c[i][j];
}
backt(0);
}
else
{ for(i=1;i<=n;++i){
for(j=1;j<=m;++j)
sc[j]+=c[i][j],sl[i]+=c[i][j];
}
backt(0);
}
cout<<ans;
return 0;
}