Cod sursa(job #1758189)

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

int n,m,l,c,mat[90][3650];
int viz[100],sol[100];
vector < pair <int ,int > > sum;
int sum_max=0;

void citire()
{
    scanf("%d%d%d%d",&n,&m,&l,&c);
    if (n>m)
    {
        for (int i=1; i<=m; ++i)
            for (int j=1; j<=n; ++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];
        }
        return;
    }
    else
    {
        sum.clear();
        for (int i=1; i<=m; ++i)
        {
            suma=0;
            for (j=1; j<=n; ++j)
                if (!viz[j])
                    suma+=mat[j][i];
            sum.push_back(make_pair(suma,i));
        }
        sort(sum.begin(),sum.end());
        suma=0;
        for (int i=c; i<sum.size(); i++)
            suma+=sum[i].first;
    }
    if (suma > sum_max)
        sum_max=suma;
}

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

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