Pagini recente » Cod sursa (job #258261) | Cod sursa (job #446162) | Cod sursa (job #10116) | Cod sursa (job #118178) | Cod sursa (job #8015)
Cod sursa(job #8015)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define max(a,b) ((a) > (b) ? (a) : (b))
int N, M, R, C, sum;
int A[1<<4][1<<12], V[1<<12], Col[1<<12];
int res;
int x[16];
void bkt(int k)
{
int i, r, j, val;
if(k == N+1)
{
for(r = 0, i = 1; i <= N; i++)
r += x[i];
if(r != R)
return ;
val = sum;
for(j = 1; j <= M; j++)
V[j] = Col[j];
for(i = 1; i <= N; i++)
if(x[i])
for(j = 1; j <= M; j++)
V[j] -= A[i][j], val -= A[i][j];
sort(V+1, V+M+1);
for(i = 1; i <= C; i++)
val -= V[i];
res = max(val, res);
}
else
x[k] = 0, bkt(k+1), x[k] = 1, bkt(k+1);
}
void read_data(void)
{
int i, j, x;
scanf("%d %d %d %d\n", &N, &M, &R, &C);
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
{
scanf("%d\n", &x), sum += x;
if(N > M)
A[M-j+1][i] = x, Col[i] += x;
else
A[i][j] = x, Col[j] += x;
}
if(N > M)
N ^= M, M ^= N, N ^= M, R ^= C, C ^= R, R ^= C;
}
void write_data(void)
{
printf("%d\n", res);
}
int main(void)
{
freopen("elimin.in", "rt", stdin);
freopen("elimin.out", "wt", stdout);
read_data();
bkt(1);
write_data();
return 0;
}