Cod sursa(job #1707585)

Utilizator david12345Rotari David david12345 Data 25 mai 2016 16:28:38
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
 
#define NMAX 8005
 
using namespace std;
 
ifstream f("elimin.in") ;
ofstream g("elimin.out") ;
 
int n , m , r , c , v[NMAX] , s , sum , sol ;
vector <vector <int> > mat ;
 
int main()
{
    f >> n >> m >> r >> c ;
 
    if(n < m){
        mat.resize(m + 5 , vector<int> (n + 5)) ;
 
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= m ; ++j){
                f >> mat[j][i] ;
                s += mat[j][i] ;
            }
        }
        swap(n , m) ;
        swap(r , c) ;
    }
 
    else{
 
 
        mat.resize(n + 5 , vector<int> (m + 5)) ;
 
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= m ; ++j){
                f >> mat[i][j] ;
                s += mat[i][j] ;
            }
        }
    }
 
    for(int i = 0 ; i < (1 << m) ; ++i){
        int nr = 0 ;
        for(int j = 0 ; j < m ; ++j){
            if((i & (1 << j)) != 0){
                ++nr ;
            }
        }
        if(nr == c){
            sum = 0 ;
            for(int j = 1 ; j <= n ; ++j){
                for(int l = 1 ; l <= m ; ++l){
                    if((i & (1 << (l - 1))) == 0){
                        v[j] += mat[j][l] ;
                    }
                    else{
                        sum += mat[j][l] ;
                    }
                }
            }
 
            sort(v + 1 , v + n + 1) ;
 
            for(int i = 1 ; i <= r ; ++i){
                sum += v[i] ;
            }
 
            sol = max(sol , s - sum) ;
            memset(v , 0 , sizeof(v)) ;
        }
    }
 
    g << sol ;
 
    return 0;
}