Pagini recente » Cod sursa (job #2304287) | Cod sursa (job #3281632) | Cod sursa (job #1869706) | Cod sursa (job #2234393) | Cod sursa (job #1527015)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define Nmax 15
#define Mmax 7300
ifstream fin("elimin.in");
ofstream fout("elimin.out");
int m, n, r, c;
int nr[1 << Nmax];
int a[Nmax][Mmax], b[Mmax][Nmax], sum[Mmax];
void solve1() ;
void solve2() ;
int main()
{
for(int i = 1; i < (1 << Nmax); ++i) nr[i] = 1 + nr[i & (i - 1)];
fin >> m >> n >> r >> c;
if(m < n) solve1();
else solve2();
return 0;
}
void solve1() // m < n => back pe linii
{
int i, j, conf, s, smax;
for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) fin >> a[i][j];
for(smax = 0, conf = 0; conf < (1 << m); ++conf)
if(nr[conf] == r)
{
for(j = 0; j < n; ++j) sum[j] = 0;
for(i = 0; i < m; ++i)
if((conf & (1 << i)) == 0)
for(j = 0; j < n; ++j) sum[j] += a[i][j];
sort(sum, sum + n, greater<int>());
for(s = 0, j = 0; j < n - c; ++j) s += sum[j];
if(s > smax) smax = s;
}
fout << smax << '\n';
}
void solve2() // m >= n => back pe coloane
{
int i, j, conf, s, smax;
for(i = 0; i < m; ++i) for(j = 0; j < n; ++j) fin >> b[i][j];
for(smax = 0, conf = 0; conf < (1 << n); ++conf)
if(nr[conf] == c)
{
for(j = 0; j < m; ++j) sum[j] = 0;
for(i = 0; i < m; ++i)
for(j = 0; j < n; ++j)
if((conf & (1 << j)) == 0)
sum[i] += b[i][j];
sort(sum, sum + m, greater<int>());
for(s = 0, j = 0; j < m - r; ++j) s += sum[j];
if(s > smax) smax = s;
}
fout << smax << '\n';
}