Cod sursa(job #1075385)

Utilizator lianaliana tucar liana Data 8 ianuarie 2014 22:06:23
Problema Elimin Scor 30
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define nmax 7300
int n, m, nl, nc, aux, i, j, st, rez, nr1;
bool sch;
int s[nmax], sol[nmax];;
int a[nmax][nmax];

void citire()
{
    scanf("%ld %ld %ld %ld",&n,&m,&nl,&nc);
    if (n<m)
    {
        aux=n;  n=m;    m=aux;
        aux=nl; nl=nc;  nc=aux;
        sch=1;
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            if (!sch)
                scanf("%ld",&a[i][j]);
            else
                scanf("%ld",&a[j][i]);
        }
}

void rezolvare()
{
    for (i=1;i<=n;i++)
    {
        s[i]=0;
        for (j=1;j<=m;j++)
            s[i]+=a[i][j]*(1-sol[j]);
    }
    sort(s+1,s+1+n);
    st=0;
    for (i=n;i>nl;i--)
        st+=s[i];
    if (st>rez)
        rez=st;
}

void gen(long poz)
{
    if(poz==m+1)
        rezolvare();
    else
    {
        if (m-poz>=nc-nr1)
        {
            sol[poz]=0;
            gen(poz+1);
        }
        if (nr1<nc)
        {
            sol[poz]=1; nr1++;
            gen(poz+1);
            nr1--;
        }
    }
}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    citire();
    rez=-1;
    gen(1);
    printf("%ld",rez);
    return 0;
}