Pagini recente » Cod sursa (job #1735663) | Cod sursa (job #2117811) | Cod sursa (job #1070674) | Cod sursa (job #2566973) | Cod sursa (job #2894623)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_M 32
#define MAX_N 8192
ifstream fin("elimin.in");
ofstream fout("elimin.out");
int M, N, R, C;
int A[MAX_M][MAX_N];
int max_sum;
int lines[MAX_M];
int column_sum[MAX_N];
void check()
{
for (int i = 1; i <= N; ++i)
column_sum[i] = 0;
for (int i = 1; i <= R; ++i)
for (int j = 1; j <= N; ++j)
column_sum[j] += A[lines[i]][j];
sort(column_sum + 1, column_sum + N + 1);
int current_sum = 0;
for (int i = N - C + 1; i <= N; ++i)
current_sum += column_sum[i];
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;
R = M - R;
C = N - 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);
}
backtracking(1);
fout << max_sum;
return 0;
}