Cod sursa(job #2065313)

Utilizator GVolterMatamare GVolter Data 13 noiembrie 2017 18:14:54
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <algorithm>

using namespace std;

int main()
{
    ifstream in("elimin.in");
    ofstream out("elimin.out");
    int a[20][8192],n,m,r,c,s[8192],v[8192],sum,smax,i,j,k,p;
    bool inv=false;
    in>>n>>m>>r>>c;
    if(n>m) k=n,n=m,m=k,k=r,r=c,c=k,inv=true;

    if(inv==true)
        for(j=1;j<=m;++j)
            for(i=1;i<=n;++i)
                in>>a[i][j];
    else
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
                in>>a[i][j];

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            s[j]+=a[i][j];

    k=(1<<n);

    for(int i=0;i<k;++i)
    {
        p=0;
        for(j=0;(1<<j)<=i;++j)
            if((1<<j)&i)
                ++p;

        if(p!=r)
            continue;
        for(j=1;j<=m;++j)
            v[j]=s[j];
        for(j=0;(1<<j)<=i;++j)
            if((1<<j)&i)
                for(p=1;p<=m;++p)
                    v[p]-=a[j+1][p];

        sort(v+1,v+m+1);

        sum=0;

        for(j=c+1;j<=m;++j)
            sum+=v[j];

        if(sum>smax) smax=sum;
    }

    out<<smax;

    return 0;
}