Cod sursa(job #1396222)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 22 martie 2015 12:02:24
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <queue>
#define nmax 600
#define ub(i) i&(-i)
using namespace std;
ifstream f("elimin.in");
ofstream g("elimin.out");
priority_queue <int> q;
int n,m,l,c,sol;
int lin[nmax],col[nmax];
int v[nmax][nmax],sum;



inline int nrbiti(int k)
{
    int i=0;
    while (k) {
        i++;
        k-=ub(k);
    }
    return i;
}

int main()
{
    int i,j,k,i1,j1;
    f>>n>>m>>l>>c;

    if (n<=m)
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
                f>>v[i][j];
    else {
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
                f>>v[j][i];
        swap(n,m);
        swap(l,c);
    }

    for (i=0;i<(1<<n);i++)
        if (nrbiti(i)==l) {
            for (j=0;j<n;j++)
                if (i&(1<<j))
                    lin[j]=0;
                else
                    lin[j]=1;
            for (j=0;j<m;j++)
                col[j]=0;

            for (i1=0;i1<n;i1++)
                for (j=0;j<m;j++)
                    if (lin[i1])
                        col[j]+=v[i1][j];

            for (j=0;j<m;j++)
                q.push(col[j]);
            k=m-c;
            sum=0;
            while (k) {
                k--;
                sum+=q.top();
                q.pop();
            }
            while (q.empty());
                q.pop();
            sol=max(sol,sum);
        }
    g<<sol<<'\n';
    return 0;
}