Cod sursa(job #1091483)

Utilizator Athena99Anghel Anca Athena99 Data 25 ianuarie 2014 18:48:55
Problema Elimin Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int nmax= 8000;
const int mmax= 16;

int a[nmax+1][mmax+1], sl[nmax+1], s[nmax+1], v[nmax+1];
int n, m, r, c, maxim;

void check(  ) {
    for ( int i= 1; i<=n; ++i ) {
        s[i]= sl[i];
        for ( int j= 1; j<=c; ++j ) {
            s[i]= s[i]-a[i][v[j]];
        }
    }
    sort( s+1, s+n+1 );

    int sol= 0;
    for ( int i= r+1; i<=n; ++i ) {
        sol+= s[i];
    }
    if ( sol>maxim ) {
        maxim= sol;
    }
}

void back( int x ) {
    if ( x==c+1 ) {
        check();
        return;
    } else {
        for ( int i= v[x-1]+1; i<=m; ++i ) {
            v[x]= i;
            back(x+1);
        }
    }
}

int main(  ) {
    fin>>n>>m>>r>>c;

    if ( n<=m ) {
        swap( n, m );
        swap( r, c );
    }
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            fin>>a[i][j];
            sl[i]+= a[i][j];
        }
    }

    back(1);
    fout<<maxim<<"\n";

    return 0;
}