Pagini recente » Cod sursa (job #1760349) | Cod sursa (job #3203564) | Cod sursa (job #1834844) | Cod sursa (job #182557) | Cod sursa (job #2894551)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <stack>
using namespace std;
#define MAX_M 50
#define MAX_N 7300
ifstream fin("elimin.in");
ofstream fout("elimin.out");
int M, N, R, C;
int A[MAX_M][MAX_N];
long long max_sum;
int lines[MAX_M];
long long column_sum[MAX_N];
void check()
{
memset(column_sum, 0, (N + 1) * sizeof(long long));
priority_queue<long long> S;
for (int j = 1; j <= N; ++j)
{
long long current = 0;
for (int i = 1; i <= R; ++i)
{
current += A[lines[i]][j];
}
S.push(current);
}
long long current_sum = 0;
for (int j = 0; j < C; ++j)
{
current_sum += S.top();
S.pop();
}
max_sum = max(max_sum, current_sum);
}
void backtracking(int step)
{
if (step == R + 1)
{
check();
return;
}
for (int i = lines[step - 1] + 1; i <= M - (R - step); ++i)
{
lines[step] = i;
backtracking(step + 1);
}
}
int main()
{
fin >> M >> N >> R >> C;
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= N; ++j)
if (M <= N)
fin >> A[i][j];
else
fin >> A[j][i];
if (M > N)
{
swap(M, N);
swap(R, C);
}
R = M - R;
C = N - C;
backtracking(1);
//cout << max_sum;
fout << max_sum;
return 0;
}