Pagini recente » Cod sursa (job #3032285) | Cod sursa (job #494027) | Cod sursa (job #2054672) | Cod sursa (job #2868571) | Cod sursa (job #8072)
Cod sursa(job #8072)
#include <cstdio>
#include <memory>
using namespace std;
const char iname[] = "elimin.in";
const char oname[] = "elimin.out";
#define MAX_M 16
#define MAX_N 1000
#define MAX_V 480005
int L[MAX_M][MAX_N];
int T[MAX_N][MAX_M];
int sum[MAX_N];
int cnt[MAX_V], X[MAX_N];
int Res;
void sort(int A[], int n) {
int i;
memset(cnt, 0, sizeof(cnt));
for (i = 0; i < n; ++i)
cnt[A[i]]++;
for (i = 1; i < MAX_V; ++i)
cnt[i] += cnt[i - 1];
for (i = n; i--; )
X[-- cnt[A[i]]] = A[i];
for (i = 0; i < n; ++i)
A[i] = X[i];
}
int main(void) {
freopen(iname, "r", stdin);
int M;
int N;
int R;
int C;
scanf("%d %d %d %d", & M, & N, & R, & C);
if (M < MAX_M) {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j)
scanf("%d", L[i] + j);
}
for (int stp = 0; stp < 1 << M; ++stp) {
int cnt = 0;
for (int i = 0; i < M; ++i)
cnt += ((stp & (1 << i)) > 0);
if (cnt == R) {
for (int j = 0; j < N; ++j) {
sum[j] = 0;
for (int i = 0; i < M; ++i)
if ((stp & (1 << i)) == 0)
sum[j] += L[i][j];
}
sort(sum, N);
int psum = 0;
for (int j = C; j < N; ++j)
psum += sum[j];
if (Res < psum)
Res = psum;
}
}
} else {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j)
scanf("%d", T[i] + j);
}
for (int stp = 0; stp < 1 << N; ++stp) {
int cnt = 0;
for (int j = 0; j < N; ++j)
cnt += ((stp & (1 << j)) > 0);
if (cnt == C) {
for (int i = 0; i < M; ++i) {
sum[i] = 0;
for (int j = 0; j < N; ++j)
if ((stp & (1 << j)) == 0)
sum[i] += T[i][j];
}
sort(sum, M);
int psum = 0;
for (int i = R; i < M; ++i)
psum += sum[i];
if (Res < psum)
Res = psum;
}
}
}
freopen(oname, "w", stdout);
printf("%d\n", Res);
return 0;
}