Cod sursa(job #2894515)

Utilizator dfettiDaniel Fetti dfetti Data 27 aprilie 2022 22:13:34
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <stack>
using namespace std;

#define MAX_M 100
#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, MAX_N * sizeof(long long));

    for (int i = 1; i <= R; ++i)
        for (int j = 1; j <= N; ++j)
        {
            column_sum[j] += A[lines[i]][j];
        }

    /*cout << "column_sum: ";
    for (int j = 1; j <= N; ++j)
        cout << column_sum[j] << ' ';
    cout << '\n';*/

    sort(column_sum + 1, column_sum + N + 1);

    long long current_sum = 0;

    for (int j = N; j >= N - C + 1; --j)
        current_sum += column_sum[j];
    //cout << "current_sum: " << current_sum << '\n';
    max_sum = max(max_sum, current_sum);
}

void backtracking(int step)
{
    //cout << "step: " << step << '\n';
    if (step == R + 1)
    {
      /*  cout << "lines:";
        for (int i = 1; i <= R; ++i)
            cout << lines[i] << ' ';
        cout << '\n';*/
        check();
        return;
    }

    for (int i = lines[step - 1] + 1; i <= M; ++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;
}