Cod sursa(job #2894551)

Utilizator dfettiDaniel Fetti dfetti Data 27 aprilie 2022 22:49:48
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#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;
}