Cod sursa(job #1758205)

Utilizator zertixMaradin Octavian zertix Data 16 septembrie 2016 19:33:19
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m,l,c,mat[90][3700];
int viz[100],sol[100];
int sum[4000];
int sum_max=0;

void citire()
{
    scanf("%d%d%d%d",&n,&m,&l,&c);
    if (n>m)
    {
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=m; ++j)
                scanf("%d",&mat[j][i]);
        swap(n,m);
        swap(l,c);
        return;
    }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; ++j)
            scanf("%d",&mat[i][j]);
}

void calc()
{
    int suma=0,j;
    if (c==0)
    {
        for (int i=1; i<=n; ++i)
        {
            if (!viz[i])
                for (int j=1; j<=m; ++j)
                    suma+=mat[i][j];
        }
    }
    else
    {
        memset(sum,0,sizeof(sum));
        for (int i=1; i<=m; ++i)
        {
            suma=0;
            for (j=1; j<=n; ++j)
                if (!viz[j])
                    suma+=mat[j][i];
            sum[i]=suma;
        }
        sort(sum+1,sum+m+1);
        suma=0;
        for (int i=c+1; i<=m; i++)
            suma+=sum[i];
    }
    if (suma > sum_max)
        sum_max=suma;
}

void combinari(int k)
{
    if (k>l)
    {
        for (int i=1;i<=l;++i)
            viz[sol[i]]=1;
        calc();
        memset(viz,0,sizeof(viz));
        return;
    }
    for (sol[k]=sol[k-1]+1; sol[k]<=n-l+k; sol[k]++)
        combinari(k+1);
}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    citire();
    combinari(1);
    printf("%d",sum_max);
    return 0;
}