Cod sursa(job #461927)

Utilizator SpiderManSimoiu Robert SpiderMan Data 9 iunie 2010 10:25:27
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
# include <cstdio>
# include <algorithm>
# include <cassert>
using namespace std;

const char FIN[] = "elimin.in", FOU[] = "elimin.out";
const int MAX = 1 << 13;

int N, M, R, C;
int V[1 << 4][MAX], sum[MAX], aux[MAX];

inline int max ( int a, int b )
{
    if ( a < b ) return b;
    return a;
}

int main()
{
    freopen ( FIN, "r", stdin );
    freopen ( FOU, "w", stdout);

    scanf ("%d %d %d %d", &N, &M, &R, &C);
    assert(N <= M);
    if ( N > M ) swap ( N, M ), swap ( R, C );

    if ( N > M )
        for (int i = 1; i <= M; ++i)
            for (int j = 1; j <= N; ++j)
                scanf ("%d", &V[j][i]);
    else
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                scanf ("%d", &V[i][j]);

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            sum[j] += V[i][j];

    int sol_f = 0;

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

        for (int j = 0; ( 1 << j ) <= i; ++j)
            if ( ( 1 << j ) & i )
                ++p;

        if ( p == R )
        {
            for (int j = 1; j <= M; ++j)
                aux[j] = sum[j];

            for (int j = 0; ( 1 << j ) <= i; ++j)
                if ( ( 1 << j ) & i )
                    for (int k = 1; k <= M; ++k)
                        aux[k] -= V[ j + 1 ][ k ];

            sort ( aux + 1 , aux + M + 1 ) ;


            int sol = 0;

            for (int j = C + 1; j <= M; ++j)
                sol += aux[j] ;

            sol_f = max ( sol_f, sol );
        }
    }

    printf("%d", sol_f);

    return 0;
}