Cod sursa(job #1511743)

Utilizator TonisonIlle Antoniu Nicolae Tonison Data 27 octombrie 2015 07:31:58
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 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 , suma , sol ;
vector <vector <int> > matrice;

int main()
{
    int x;
     f>>n>>m>>r>>c;
     if(n < m)
    {
        matrice.resize(m + 5 , vector<int> (n + 5)) ;

        for(int i = 1 ; i <= n ; ++i)
        {
            for(int j = 1 ; j <= m ; ++j)
            {
                f >> matrice[j][i] ;
                s += matrice[j][i] ;
            }
        }
        x=n;    n=m;    m=x;
        x=r;    r=c;    c=x;
    }
    else
    {
        matrice.resize(n + 5 , vector<int> (m + 5)) ;
        for(int i = 1 ; i <= n ; ++i)
        {
            for(int j = 1 ; j <= m ; ++j)
            {
                f >> matrice[i][j];
                s += matrice[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)
        {
            suma = 0 ;
            for(int j = 1 ; j <= n ; ++j)
            {
                for(int l = 1 ; l <= m ; ++l)
                {
                    if((i & (1 << (l - 1))) == 0)
                    {
                        v[j] += matrice[j][l] ;
                    }
                    else
                    {
                        suma += matrice[j][l] ;
                    }
                }
            }

            sort(v + 1 , v + n + 1) ;

            for(int i = 1 ; i <= r ; ++i)
            {
                suma += v[i] ;
            }
            sol = max(sol , s - suma) ;
            memset(v , 0 , sizeof(v)) ;
        }
    }
    g << sol ;
    return 0;
}