Cod sursa(job #2398664)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 5 aprilie 2019 20:19:24
Problema Elimin Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int N, M, C, L;
int a[530][20];
long long smax = 0;
int s_l[530];


bool cmp(int a, int b)
{
    return a>=b;
}


void citire_normala(int N, int M)
{
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
        {
            scanf("%d", &a[i][j]);
            s_l[i] += a[i][j];
        }
}

void citire_rotated(int N, int M)
{
    for(int i=1; i <= N; i++)
        for(int j=1; j<=M; j++)
        {
            scanf("%d", &a[j][i]);
            s_l[i] += a[j][i];
        }
}


void copiaza(int csl[])
{
    for(int i=1; i<=N; i++)
        csl[i] = s_l[i];
}


void verif(int x)
{
    int copie_s_l[530];
    copiaza(copie_s_l);

    int s_actual = 0;
    int j;

    for(j=M; j>0 && x; j--, x>>=1)
        if((x&1) != 0)
            for(int i=1; i<=N; i++)
                copie_s_l[i] -= a[i][j];


    sort(copie_s_l+1, copie_s_l + N + 1, cmp);

    for(int i=1; i<=N-L; i++)
        s_actual += copie_s_l[i];

    if(s_actual > smax)
        smax = s_actual;
}




void generare()
{
    int v = (1<<M);
    for(int i=0; i<v; i++)
    {
        int nr1 = C;
        int x = i;
        for(int j=0; x; j++, x>>=1)
            if((x&1) != 0)
                nr1--;
        if(nr1 == 0)
            verif(i);
    }

}


int main() {
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);
    scanf("%d %d %d %d", &N, &M, &L, &C);
    if(M <= N)
        citire_normala(N, M);
    else{
        swap(N, M);
        swap(L, C);
        citire_rotated(N, M);
    }
    generare();
    printf("%d", smax);
    return 0;
}