Cod sursa(job #1333570)

Utilizator wGEORGEWGeorge Cioti wGEORGEW Data 3 februarie 2015 12:46:19
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
ifstream fin ("elimin.in");
ofstream fout ("elimin.out");
int N, M, R, C, S[20], F[8000], V[20][8000];
bitset < 20 > fr;
 
int main()
{
    fin >> N >> M >> R >> C;
    if (N <= M)
    {
        for (int i=1; i<=N; i++)
        {
            for (int j=1; j<=M; j++)
            {
                fin >> V[i][j];
            }
        }
    }
    else
    {
        for (int i=1; i<=N; i++)
        {
            for (int j=1; j<=M; j++)
            {
                fin >> V[j][i];
            }
        }
        swap (N, M);
        swap (R, C);
    }
 
    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=M; j++)
        {
            S[i] += V[i][j];
        }
    }
 
    int maxim = 0;
    for (int i=0; i<(1 << N); i++)
    {
        int nr = 0, sum = 0;
        for (int j=1; j<=N; j++)
        {
            if (i & (1 << (j-1)))
            {
                nr++;
                fr[j] = 1;
            }
        }
 
        if (nr == R)
        {
            for (int j=1; j<=M; j++)
            {
                F[j] = 0;
                for (int k=1; k<=N; k++)
                {
                    if (!fr[k])
                    {
                        F[j] += V[k][j];
                    }
                }
            }
            sort (F + 1, F + 1 + M);
            for (int k=C+1; k<=M; k++)
            {
                sum += F[k];
            }
            if (sum > maxim) maxim = sum;
        }
        fr.reset();
    }
 
    fout << maxim << '\n';
    fout.close();
    return 0;
}