Cod sursa(job #2197478)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 22 aprilie 2018 12:11:10
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, r, c;// se da o matrice de n pe m si trebuie sa elimin exact r linii si c coloane
int matr[200][200];//matricea contine numere naturale
int linie[200],sumCol[200];
int sumMax, nrLin;

void citire(){
    in >> n >> m >> r >> c;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            in >> matr[i][j];
        }
    }
}

void quickSort(int st, int dr){
    int i = st, j = dr, pivot = (st + dr)/2;
    while(i <= j){
        while(i <= dr && sumCol[i] < sumCol[pivot]){
            i++;
        }
        while (j >= st && sumCol[j] > sumCol[pivot]){
            j--;
        }
        if(i <= j){
            int temp = sumCol[i];
            sumCol[i] = sumCol[j];
            sumCol[j] = temp;
            i++;
            j--;
        }
    }
    if(i < dr){
        quickSort(i, dr);
    }
    if(j > st){
        quickSort(st, j);
    }

}

void sumaColoane(){
    int sumTemp = 0;

    for(int i = 1; i <= m; i++){
        sumCol[i] = 0;
    }
    for(int i = 1; i <= nrLin; i++){
        for(int j = 1; j <= m ;j++){
            sumCol[j] = sumCol[j] + matr[linie[i]][j];
        }
    }
    quickSort(1, m);
    for(int i = m; i > c; i--){
        sumTemp = sumTemp + sumCol[i];
    }
    if(sumTemp > sumMax){
        sumMax = sumTemp;
    }

}

void bktLinii(int varf){
    for(int i = linie[varf - 1] + 1; i <= n; i++){
        linie[varf] = i;
        if(varf <= nrLin){
            if(varf == nrLin){
                sumaColoane();
            }else{
                bktLinii(varf + 1);
            }
        }
    }
}

int main() {
    citire();
    nrLin = n - r;
    bktLinii(1);
    out << sumMax;
    return 0;
}