Pagini recente » Cod sursa (job #2680792) | Cod sursa (job #1316825) | Cod sursa (job #1599665) | Cod sursa (job #2530985) | Cod sursa (job #711313)
Cod sursa(job #711313)
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
unsigned short h[530][530];
bool gen[20];
int n,m,r,c;
vector<int> v;
long long maxim=-1<<30;
void back(int niv,int nr) // c coloane
{
if(niv==n+1)
{
if(nr==c)
{
// for(int i=1;i<=n;i++)
// cout<<gen[i]<<" ";
//cout<<endl;
v.clear();
long long S=0;
for(int i=1;i<=m;i++)
{
S=0;
for(int j=1;j<=n;j++)
if(gen[j]==0)
S+=h[i][j];
v.push_back(S);
}
S=0;
sort(v.begin(),v.end());
for(int i=v.size()-1;i>=r;i--)
S+=v[i];
maxim=max(S,maxim);
}
return;
}
if(nr<=c)
{
gen[niv]=1;
back(niv+1,nr+1);
gen[niv]=0;
}
back(niv+1,nr);
}
void back2(int niv,int nr) // r linii
{
if(niv==n+1)
{
if(nr==r)
{
// for(int i=1;i<=n;i++)
// cout<<gen[i]<<" ";
// cout<<endl;
v.clear();
long long S=0;
for(int i=1;i<=n;i++)
{
S=0;
for(int j=1;j<=m;j++)
if(gen[j]==0)
S+=h[j][i];
v.push_back(S);
}
S=0;
sort(v.begin(),v.end());
for(int i=v.size()-1;i>=c;i--)
S+=v[i];
maxim=max(S,maxim);
}
return;
}
if(nr<=r)
{
gen[niv]=1;
back(niv+1,nr+1);
gen[niv]=0;
}
back(niv+1,nr);
}
int main()
{
freopen("elimin.in","r", stdin);
freopen("elimin.out","w", stdout);
scanf("%d %d %d %d\n",&m,&n,&r,&c); // m linii si n coloane
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d ",&h[i][j]);
if(c<=r) // nr coloanelor
{
back(1,0);
printf("%lld",maxim);
}
else // nr linii mai mare
{
back2(1,0);
printf("%lld",maxim);
}
return 0;
}