Cod sursa(job #1075425)

Utilizator lianaliana tucar liana Data 8 ianuarie 2014 22:51:34
Problema Elimin Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.4 kb
#include<stdio.h>
#include<set>
using namespace std;
#define nmax 7295
int n, m, nl, nc, aux, i, j, st, rez, nr1, poz, conf, cmax, x, nb, s;
bool sch;
multiset <int> h;
multiset <int> ::iterator it;
short a[nmax][nmax];

void citire()
{
    scanf("%ld %ld %ld %ld",&n,&m,&nl,&nc);
    if (n<m)
        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]);
        }
    if(sch)
    {
        aux=n;  n=m;    m=aux;
        aux=nl; nl=nc;  nc=aux;
    }
}

void rezolvare()
{
    h.clear();
    for (i=1;i<=n;i++)
    {
        s=0;
        for (j=1;j<=m;j++)
            if (((1<<j)&conf)==0)
                s+=a[i][j];
        h.insert(s);
        if (i>m-nc)
        {
            it=h.end(); it--;
            h.erase(h.begin());
        }
    }
    st=0;
    for (it=h.begin();it!=h.end();it++)
        st+=*it;
    if (st>rez)
        rez=st;
}

void gen()
{
    cmax=(1<<(m+1))-1;
    for (conf=0;conf<=cmax;conf+=2)
    {
        x=conf; nb=0;
        while (x>0)
        {   x=x&(x-1);   nb++;   }
        if (nb==nc)
            rezolvare();
    }
}

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