Cod sursa(job #1017471)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 octombrie 2013 19:51:46
Problema Elimin Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 1000;

int N, M, R, C, sum_max = -1e8;
int A[Nmax][Nmax];
int st[Nmax];

void read()
{
    ifstream f("elimin.in");

    f >> N >> M >> R >> C;

    if ( N <= M )
    {
        for ( int i = 1; i <= N; ++i )
                for ( int j = 1; j <= M; ++j )
                        f >> A[i][j];
    }
    else
    {
        for ( int i = 1; i <= M; ++i )
                for ( int j = 1; j <= N; ++j )
                        f >> A[i][j];

        swap( N, M );
        swap( R, C );
    }

    f.close();
}

void solve()
{
    int use[Nmax] = { 0 };
    int randuri[Nmax] = { 0 };
    int cont = 0;
    int suma = 0;

    for ( int i = 1; i <= C; ++i )
    {
        use[ st[i] ] = 1;
    }

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

        for ( int j = 1; j <= M; ++j )
        {
            if ( use[j] ) continue;

            randuri[cont] += A[i][j];
        }
    }

    sort( randuri + 1, randuri + 1 + cont );

    for ( int i = cont; i >= R + 1; i-- )
    {
        suma += randuri[i];
    }

    sum_max = max( suma, sum_max );
}

void back( int k )
{
    if ( k > C )
            solve();
    else
        for ( int i = st[k - 1] + 1; i <= M - C + k; ++i )
        {
            st[k] = i;
            back( k + 1 );
        }
}

void print()
{
    ofstream g("elimin.out");

    g << sum_max << "\n";

    g.close();
}

int main()
{
    read();
    back( 1 );
    print();

    return 0;
}