Cod sursa(job #1013928)

Utilizator maritimCristian Lambru maritim Data 21 octombrie 2013 21:56:24
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");

#define MaxN 20
#define MaxM 7100

int N,M,R,C,Sol;
int A[MaxN][MaxM];
int V[MaxN],viz[MaxN],B[MaxM];

void citire(void)
{
    f >> N >> M >> R >> C;

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

        int aux = N; N = M; M = aux;
        aux = R; R = C; C = aux;
    }
    else
    {
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
                f >> A[i][j];
    }
}

inline int newSol(int val)
{
    int Sol = 0;

    for(int i=1;i<=M;i++)
        B[i] = 0;

    for(int i=1;i<=N;i++)
        if(val&(1<<(i-1)))
            for(int j=1;j<=M;j++)
                B[j] += A[i][j];

    nth_element(B+1,B+C+1,B+M+1);

    for(int i=C+1;i<=M;i++)
        Sol += B[i];

    return Sol;
}

void back(void)
{
    int nr = 0;

    for(int i=0;i<(1<<N);i++)
    {
        nr = 0;

        for(int j=0;j<N;j++)
            nr += ((i & (1<<j)) ? 1 : 0); 

        if(nr == (N-R))
            Sol = max(Sol,newSol(i));
    }
}

int main()
{
    citire();
    back();
    
    g << Sol << "\n";
}