Pagini recente » Cod sursa (job #899658) | Cod sursa (job #1910927) | Cod sursa (job #462999) | Cod sursa (job #2954170) | Cod sursa (job #1014046)
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
const int MAXN = 2 * 7 * 521;
const int MAXM = 20;
using namespace std;
int Col[MAXN];
int M, N, R, C;
int total_sum;
int ord[MAXN];
int ans;
int A[MAXN][MAXM], rem[MAXN];
int t;
inline bool cmp(const int& a, const int& b){
return Col[a] < Col[b];
}
void back(int k) {
if (k > R) {
int _s = total_sum - t;
nth_element(ord, ord + C, ord + N, cmp);
for (int j = 0; j < C; ++j) {
_s -= Col[ord[j]];
}
if (ans < _s) {
ans = _s;
}
} else {
for (int i = rem[k - 1] + 1; i <= M; ++i) {
rem[k] = i;
for (int j = 0; j < N; ++j) {
Col[j] -= A[rem[k] - 1][j];
t += A[rem[k] - 1][j];
}
back(k + 1);
for (int j = 0; j < N; ++j) {
Col[j] += A[rem[k] - 1][j];
t -= A[rem[k] - 1][j];
}
}
}
}
int main() {
ifstream cin("elimin.in");
ofstream cout("elimin.out");
cin >> M >> N >> R >> C;
//back pe linii
if (M < N) {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> A[i][j];
}
}
} else {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> A[j][i] ;
}
}
swap(M, N);
swap(R, C);
}
for (int i = 0; i < N; ++i)
ord[i] = i;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
Col[j] += A[i][j]; total_sum += A[i][j];
}
}
back(1);
cout << ans << "\n";
return 0;
}