Cod sursa(job #2894641)

Utilizator dfettiDaniel Fetti dfetti Data 28 aprilie 2022 00:07:42
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb

#include <bits/stdc++.h>
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;
}