Pagini recente » Cod sursa (job #1121175) | Cod sursa (job #2890691) | Cod sursa (job #1873009) | Cod sursa (job #420280) | Cod sursa (job #6891)
Cod sursa(job #6891)
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MARE = 8000;
const int MIC = 20;
int M, N, R, C, S = 0, sf, MAX = 0;
int a[MIC][MARE], st[MIC], sml[MIC], smc[MARE], smc2[MARE], is[MIC];
void back(int k)
{
int i, j;
if (k == R + 1) {
for (i = 1; i <= N; i ++) {
smc2[i] = smc[i];
for (j = 1; j <= M; j ++) {
if (is[j]) {
smc2[i] -= a[j][i];
}
}
}
sort(smc2 + 1, smc2 + N + 1);
sf = S;
for (i = 1; i <= C; i ++) {
sf -= smc2[i];
}
if (sf > MAX) {
MAX = sf;
}
} else {
for (int c = 1; c <= M; c ++) {
if (!is[c]) {
is[c] = 1;
S -= sml[c];
back(k + 1);
is[c] = 0;
S += sml[c];
}
}
}
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
int aux, i, j;
scanf("%d %d %d %d\n", &M, &N, &R, &C);
if (M < N) {
for (i = 1; i <= M; i ++) {
for (j = 1; j <= N; j ++) {
scanf("%d ", &a[i][j]);
S += a[i][j];
sml[i] += a[i][j];
smc[j] += a[i][j];
}
}
} else {
for (i = 1; i <= M; i ++) {
for (j = 1; j <= N; j ++) {
scanf("%d ", &a[N - j + 1][i]);
S += a[N - j + 1][i];
sml[N - j + 1] += a[N - j + 1][i];
smc[i] += a[N - j + 1][i];
}
}
aux = M;
M = N;
N = aux;
aux = C;
C = R;
R = aux;
}
back(1);
printf("%d\n", MAX);
return 0;
}