Pagini recente » Cod sursa (job #61964) | Cod sursa (job #2386668) | Cod sursa (job #333235) | Cod sursa (job #1497936) | Cod sursa (job #1466397)
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <assert.h>
#define MAX_N 63
#define MAX_M 7294
#define NIL -1
short a[MAX_M][MAX_N];
int sum[MAX_M];
short next[MAX_N];
inline int buildList(const unsigned long long &p, const int &n) {
int i;
int prev;
memset(next, NIL, sizeof(next));
i = 0;
while (p & (1ULL << i)) {
i++;
}
prev = i;
i++;
for (; i < n; i++) {
if (!(p & (1ULL << i))) {
next[i] = prev;
prev = i;
}
}
return prev;
}
/*
inline void printBits(const unsigned long long &p) {
for (int i = 0; i < 64; i++) {
if (p & (1ULL << i)) {
putchar('1');
} else {
putchar('0');
}
}
putchar('\n');
} */
int main(void) {
FILE *f = fopen("elimin.in", "r");
int n, m, r, c;
int ans, q;
unsigned long long currentPerm, nextPerm, t;
fscanf(f, "%d%d%d%d", &n, &m, &r, &c);
if (n <= m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
fscanf(f, "%hd", &a[j][i]);
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
fscanf(f, "%hd", &a[i][j]);
}
}
std::swap(n, m);
std::swap(r, c);
}
fclose(f);
nextPerm = (1ULL << r) - 1;
ans = 0;
do {
currentPerm = nextPerm;
q = buildList(currentPerm, n);
for (int i = 0; i < m; i++) {
sum[i] = 0;
for (int j = q; j != NIL; j = next[j]) {
sum[i] += a[i][j];
}
}
std::make_heap(sum, sum + m);
q = 0;
for (int i = 0; i + c < m; i++) {
q += sum[0];
std::pop_heap(sum, sum + m - i);
}
if (q > ans) {
ans = q;
}
t = (currentPerm | (currentPerm - 1)) + 1;
nextPerm = t | ((((t & -t) / (currentPerm & -currentPerm)) >> 1ULL) - 1);
} while (nextPerm < (1ULL << n));
f = fopen("elimin.out", "w");
fprintf(f, "%d\n", ans);
fclose(f);
return 0;
}