Pagini recente » Cod sursa (job #2797973) | Cod sursa (job #190896) | Cod sursa (job #878574) | Cod sursa (job #2222494) | Cod sursa (job #2894636)
#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()
{
ios::sync_with_stdio(0);
cin.tie(0);
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;
}