Cod sursa(job #1022175)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 4 noiembrie 2013 21:30:48
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 700;

int V[NMAX][NMAX], newS[NMAX], sum[NMAX], Value[NMAX];
int N, M, R, C, maxSolution = -1;

void newValue(){
    int sol = 0, i, j;

    for(i = 1; i <= N; i++){

        newS[i] = sum[i];
        for(j = 1; j <= C; j++){
            newS[i] -= V[i][Value[j]];
        }
    }

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

    for(i = R+1; i <= N; i++)
        sol += newS[i];

    if(sol > maxSolution)
        maxSolution = sol;
}

void back(int pos){
    if(pos > C){
        newValue();
    }
    else {
        for(int i = Value[pos-1] + 1; i <= N; i++){
            Value[pos] = i;
            back(pos+1);
        }
    }
}

int main()
{
    int i,j;
    in >> N >> M >> R >> C;
    if( N > M){

        for(i = 1; i <= N; i++)
            for(j = 1; j <= M; j++){
                in >> V[j][i];

                sum[j] += V[j][i];
            }
        swap(N,M);
        swap(R,C);
    }
    else for(i = 1; i <= N; i++)
            for(j = 1; j <= M; j++){
                in >> V[i][j];
                sum[i] += V[i][j];
            }
    back(1);

    out << maxSolution;
    return 0;
}