Cod sursa(job #1002301)

Utilizator poptibiPop Tiberiu poptibi Data 27 septembrie 2013 13:36:07
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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;
}