Cod sursa(job #1240499)

Utilizator gerd13David Gergely gerd13 Data 11 octombrie 2014 14:39:03
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>

using namespace std ;

const int NMAX = 8500 ;
const int INF = 0x3f3f3f3f ;

ifstream cin("elimin.in") ;
ofstream cout("elimin.out") ;

int N, M, R, C;
int A[NMAX][NMAX] ;
int s[NMAX], D[NMAX] ;
int sol = -INF ;


void Back(int K, int L)
{

    if(K == R + 1)
    {
        for(int i = 1 ; i <= N ; ++ i)
            for(int j = 1 ; j <= M ; ++ j )
                s[j] = s[j]  + A[i][j] * ( (D[i] + 1) % 2) ;

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

        int suma = 0 ;

        for(int i = M ; i > C ; -- i )
            suma = suma + s[i] ;

        if(suma > sol)
            sol = suma ;

        memset(s, 0, sizeof(s)) ;
    }
    else for(int i = L + 1 ; i <= N ; ++ i)
        {
            D[i] = 1;
            Back(K +1, i) ;
            D[i] = 0 ;
        }

}





int main()
{

    cin >> N >> M >> R >> C ;

    if(N > 20)
    {
        for(int i = 1 ; i <= N ; ++ i )
            for(int j = 1 ; j<= M ; ++ j)
                cin >> A[j][i] ;

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

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

    Back(1, 0);

    cout << sol << '\n' ;



    cin.close() ;
    cout.close() ;
    return  0 ;
}