Cod sursa(job #2515329)

Utilizator dragos99Homner Dragos dragos99 Data 28 decembrie 2019 13:13:54
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<fstream>
#include<algorithm>
using namespace std;
    ifstream f("elimin.in");
    ofstream g("elimin.out");

long stivaLinie[1001], sumColoana[1001], v[1001][1001];
long n, m, r, c, maxim, numarLinii;

void sumaColoane()
{
    long i, j, sum = 0 ;
    for(i = 1 ; i <= m ; i++)
        sumColoana[i] = 0;
    for(i = 1 ; i <= numarLinii ; i++){
        for(j = 1 ; j <= m ; j++){
            sumColoana[j] += v[stivaLinie[i]][j];
        }
    }
    sort(sumColoana + 1, sumColoana + m + 1);
    for(i = m ; i > c ; i--)
        sum += sumColoana[i];
    if(sum > maxim)
        maxim = sum;
}

void backtracking(long nivel)
{
    int i;
    for(i = stivaLinie[nivel - 1] + 1 ; i <= n ; i++){
        stivaLinie[nivel] = i;
        if(nivel == numarLinii)
            sumaColoane();
        else
            backtracking(nivel + 1);

    }
}

int main()
{
    long i, j;
    f>>n>>m>>r>>c;
    for(i = 1 ; i <= n ; i++)
        for(j = 1 ; j <= m ; j++){
            if(n < m)
                f>>v[i][j];
            else
                f>>v[j][i];
        }
    if(n > m){
        swap(r, c);
        swap(n, m);
    }

    numarLinii = n - r;

    backtracking(1);

    g<<maxim;

    return 0;
}