Pagini recente » Cod sursa (job #214789) | Cod sursa (job #938989) | Cod sursa (job #1705952) | Cod sursa (job #59345) | Cod sursa (job #695882)
Cod sursa(job #695882)
#include <cstdio>
#include <algorithm>
#define MMAX 8192
#define NMAX 128
using namespace std;
short a[MMAX][NMAX];
int cols[NMAX], rows[MMAX], sol;
int N, M, R, C;
int check(int k)
{
int nr = 0;
for(int i=0;i<=k;++i)
{
nr += cols[i];
}
if(nr > C)
{
return 0;
}
if(nr + N - k - 1 < C)
{
return 0;
}
return 1;
}
void update()
{
for(int i=0;i<M;++i) rows[i] = 0;
for(int j=0;j<N;++j)
{
if(!cols[j])
{
for(int i=0;i<M;++i)
{
rows[i] += a[i][j];
}
}
}
sort(rows, rows+M);
int sum = 0;
for(int i=M-1;i>=R;--i)
{
sum += rows[i];
}
if(sum > sol)
{
sol = sum;
}
}
void back(int k)
{
if(k == N)
{
update();
}
else
{
for(int i=0;i<2;++i)
{
cols[k] = i;
if(check(k))
{
back(k+1);
}
}
}
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%d %d %d %d", &M, &N, &R, &C);
if(M >= N)
{
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
scanf("%d", &a[i][j]);
}
else
{
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
scanf("%d", &a[j][i]);
swap(N,M);
swap(R,C);
}
back(0);
printf("%d", sol);
return 0;
}