Cod sursa(job #1017527)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 octombrie 2013 20:49:19
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 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 * 10][30];
int randuri[Nmax * 10];
int sum_rand[Nmax * 10];

inline void scan( int &n )
{
    n = 0;

    int ch = getchar();
    int sign = 1;

    while ( ch < '0' || ch > '9' )
    {
        if ( ch == '-')
            sign = -1;

        ch = getchar();
    }

    while (  ch >= '0' && ch <= '9' )
    {
        n = ( n << 3 ) + ( n << 1) + ch - '0';
        ch = getchar();
    }

    n = n * sign;
}

void read()
{
    freopen("elimin.in", "r", stdin);

    scan( N );
    scan( M );
    scan( R );
    scan( C );

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

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

    for ( int i = 1; i <= N; ++i )
                for ( int j = 1; j <= M; ++j )
                        sum_rand[i] += A[i][j];

    fclose( stdin );
}

void back()
{
    int lim = 1 << M;

    for ( int i = 0; i < lim; ++i )
    {
        int s = 0;

        for ( int k = 1; k <= N; ++k )
                randuri[k] = sum_rand[k];

        for ( int j = 0; j < M; ++j )
        {
            if ( i & ( 1 << j ) )
            {
                for ( int k = 1; k <= N; ++k )
                {
                    randuri[k] -= A[k][j + 1];
                }

                s++;
            }
        }

        if ( s == C )
        {
            int suma = 0;

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

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

            sum_max = max( suma, sum_max );
        }
    }
}

void print()
{
    freopen("elimin.out", "w", stdout);

    printf("%d\n", sum_max);

    fclose( stdout );
}

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

    return 0;
}