Cod sursa(job #1066072)

Utilizator poptibiPop Tiberiu poptibi Data 23 decembrie 2013 23:46:28
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.27 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 605;

int M, N, R, C, A[NMAX][NMAX], V[NMAX], Out[NMAX], Ans;

void Back(int Pos, int Last)
{
    if(Pos == R + 1)
    {
        for(int i = 1; i <= N; ++ i) V[i] = 0;
        for(int i = 1; i <= M; ++ i)
            if(!Out[i])
                for(int j = 1; j <= N; ++ j)
                    V[j] += A[i][j];
        nth_element(V + 1, V + C , V + N + 1);

        int Now = 0;
        for(int i = N; i > C; -- i)
            Now += V[i];

        Ans = max(Ans, Now);

        return ;
    }

    for(int i = Last + 1; i <= M - R + Pos; ++ i)
    {
        Out[i] = 1;
        Back(Pos + 1, i);
        Out[i] = 0;
    }
}

int main()
{
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);

    scanf("%i %i %i %i", &M, &N, &R, &C);
    if(M <= N)
    {
        for(int i = 1; i <= M; ++ i)
            for(int j = 1; j <= N; ++ j)
                scanf("%i", &A[i][j]);
    }else
    {
        for(int i = 1; i <= M; ++ i)
            for(int j = 1; j <= N; ++ j)
                scanf("%i", &A[j][i]);
        swap(N, M);
        swap(R, C);
    }

    Back(1, 0);

    printf("%i\n", Ans);

    return 0;
}