Cod sursa(job #1945909)

Utilizator adystar00Bunea Andrei adystar00 Data 29 martie 2017 19:03:54
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,r,c;
bool seen[8000];
int a[20][8000],d[20][8000],sum[8000],maxx=0;
void check()
{
    int i,j,k=0,t,suma=0;
    for(i=0; i<n; i++)
    {
        if(seen[i]==true)
            continue;
        for(j=0; j<m; j++)
            d[k][j]=a[i][j];
        k++;
    }
    for(j=0; j<m; j++)
    {
        sum[j]=0;
        for(t=0; t<k; t++)
            sum[j]+=d[t][j];
    }
    sort(sum,sum+m);
    for(j=c; j<m; j++)
        suma+=sum[j];
    if(suma>maxx)
        maxx=suma;
}
void backtracking(int niv,int poz)
{
    int i;
    if(niv==r)
    {
        check();
        return;
    }
    for(i=poz; i<n; i++)
    {
        seen[i]=true;
        backtracking(niv+1,i+1);
        seen[i]=false;
    }
}
int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    int i,j,aux;
    scanf("%d%d%d%d",&n,&m,&r,&c);
    if(n>m)
    {
        aux=n;
        n=m;
        m=aux;
        aux=r;
        r=c;
        c=aux;
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
                scanf("%d",&a[j][i]);
    }
    else
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                scanf("%d",&a[i][j]);
    backtracking(0,0);
    printf("%d",maxx);
    return 0;
}