Cod sursa(job #1260880)

Utilizator gedicaAlpaca Gedit gedica Data 11 noiembrie 2014 18:39:23
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int NMAX= 20, MMAX= 8000, inf= 1<<30;

int A[NMAX+1][MMAX+1];
int N, M, l, c, sol=-inf;

int s[MMAX+1], u[NMAX+1];

void backtrack( int x, int last )
{
    if ( x==l+1 )
    {
        for ( int i= 1; i<=N; ++i )
        {
            for ( int j= 1; j<=M; ++j )
            {
                s[j]+= A[i][j]*( (u[i]+1)%2 );
            }
        }
        sort( s+1, s+M+1 );
        int sum= 0;
        for ( int i= M; i>c; --i )
        {
            sum+= s[i];
        }
        if ( sum>sol )
        {
            sol= sum;
        }
        for ( int i= 1; i<=M; ++i )
        {
            s[i]= 0;
        }
    }
    else
    {
        for ( int i= last+1; i<=N; ++i )
        {
            u[i]= 1;
            backtrack(x+1, i);
            u[i]= 0;
        }
    }
}

int main(  )
{
    in >> N >> M >> l >> c;
    if ( N>NMAX )
    {
        for ( int i= 1; i<=N; ++i )
        {
            for ( int j= 1; j<=M; ++j )
            {
                in >> A[j][i];
            }
        }
        swap(N, M), swap(l, c);
    }
    for ( int i= 1; i<=N; ++i )
    {
        for ( int j= 1; j<=M; ++j )
        {
            in >> A[i][j];
        }
    }
    backtrack(1,0);
    out << sol << '\n';
    return 0;
}