Cod sursa(job #328507)

Utilizator freak93Adrian Budau freak93 Data 2 iulie 2009 13:01:40
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");

int a[20][8000],i,j,n,m,k,p,r,c,s[8000],b[8000],st,stmax;
bool inv;

int main()
{
    f>>n>>m>>r>>c;
    if(n>m) k=n,n=m,m=k,k=r,r=c,c=k,inv=true;

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(inv)
                f>>a[j][i],s[i]+=a[j][i];
            else
                f>>a[i][j],s[j]+=a[i][j];

    k=(1<<n);

    for(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)
            b[j]=s[j];
        for(j=0;(1<<j)<=i;++j)
            if((1<<j)&i)
                for(p=1;p<=m;++p)
                    b[p]-=a[j+1][p];

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

        st=0;

        for(j=r+1;j<=m;++j)
            st+=b[j];

        if(st>stmax) stmax=st;
    }

    g<<stmax<<"\n";

    f.close();
    g.close();

    return 0;
}