Cod sursa(job #1060682)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 18 decembrie 2013 13:53:30
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 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];

const int DIM_BUFF = ( 1 << 20 );

char buffer[DIM_BUFF];
int position = DIM_BUFF;

char GetChar()
{
    if ( position == DIM_BUFF )
    {
        fread( buffer, 1, DIM_BUFF, stdin );
        position = 0;
    }

    return buffer[ position++ ];
}

int rd()
{
    int nr = 0;
    char c;

    do
    {
        c = GetChar();

    } while ( !isdigit( c ) );

    do
    {
        nr = nr * 10 + ( c - '0' );
        c = GetChar();

    } while ( isdigit( c ) );

    return nr;
}

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

    N = rd(); M = rd(); R = rd(); C = rd();

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

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

    fclose( stdin );
}

void solve( int numar )
{
    int cont = 0;
    int suma = 0;

    for ( int i = 1; i <= N; ++i )
    {
        cont++;
        randuri[i] = 0;

        for ( int j = 1; j <= M; ++j )
        {
            if ( numar & ( 1 << ( j - 1 ) ) ) 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 lim = 1 << M;

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

        for ( int j = 0; j < M; ++j )
        {
            if ( i & ( 1 << j ) )
                    s++;
        }

        if ( s == C )
        {
            solve( i );
        }
    }
}

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

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

    fclose( stdout );
}

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

    return 0;
}