Pagini recente » Cod sursa (job #1943241) | Cod sursa (job #1942077) | Cod sursa (job #269130) | Cod sursa (job #2119602) | Cod sursa (job #1014031)
#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 = 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];
inline bool cmp(const int& a, const int& b){
return Col[a] < Col[b];
}
void back(int k) {
if (k == R) {
int tmp = total_sum;
nth_element(ord, ord + C, ord + N, cmp);
for (int j = 0; j < C; ++j) {
tmp -= Col[ord[j]];
// cerr << Col[ord[j]] << " " ;
}
if (ans < tmp) {
ans = tmp;
}
} else {
for (int i = rem[k - 1] + 1; i <= M; ++i) {
rem[k] = i;
for (int j = 0; j < N; ++j) {
Col[j] -= A[i - 1][j];
total_sum -= A[i - 1][j];
}
back(k + 1);
for (int j = 0; j < N; ++j) {
Col[j] += A[i - 1][j];
total_sum += A[i - 1][j];
}
}
}
}
int main() {
ifstream cin("elimin.in");
ofstream cout("elimin.out");
cin >> M >> N >> R >> C;
for (int i = 0; i < N; ++i)
ord[i] = i;
//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 < M; ++i) {
for (int j = 0; j < N; ++j) {
Col[j] += A[i][j]; total_sum += A[i][j];
}
}
back(0);
cout << ans << "\n";
return 0;
}