Cod sursa(job #2519456)

Utilizator alexnigaNiga Alexandru alexniga Data 7 ianuarie 2020 19:29:26
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");

int m, n, r, c, x[1010][1010], linie[1010], sum_col[1010], raspuns;

void realoc_zero(int v[], int n)
{
    int i;
    for (i = 0; i <= n; i++)
        v[i] = 0;
}

void calcu_sum_col()
{
    int i, j, sum_max = 0;

    realoc_zero(sum_col, m);

    for (i = 1; i <=n; i++)
        for (j = 1; j <=m; j++)
            sum_col[j] = sum_col[j] + x[linie[i]][j];

    sort(sum_col + 1, sum_col + m + 1);

    for (i = m; i > c; i--)
        sum_max += sum_col[i];

    if (sum_max > raspuns)
        raspuns = sum_max;
}

void backt(int p)
{
    long long i = linie[p - 1] + 1;

    while(i <= n)
    {
        linie[p] = i;
        if (p == n - r)
            calcu_sum_col();
        else
            backt(p + 1);
        ++i;
    }
}

int main()
{
    int i, j, aux;

    f >> n >> m >> r >> c;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
    {
            if (n < m)
                f >> x[i][j];
            else
                f >> x[j][i];
    }
    if (n > m)
    {
        aux = n; n = m;
        m = aux;
        aux = c; c = r;
        r = aux;
    }
    backt(1);
    g << raspuns;


    return 0;
}