Cod sursa(job #461920)

Utilizator SpiderManSimoiu Robert SpiderMan Data 9 iunie 2010 08:38:23
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<algorithm>

using namespace std;

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

int a[16][8192],i,j,n,m,k,p,r,c,s[8192],b[8192],st,stmax;
bool inv=false;

int main()
{
    f>>n>>m>>r>>c;

    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            f>>a[i][j];
        }
    }
    if (n<m)
    {
        for (i=1; i<=n; i++)
        {
            for (j=1; j<=m; j++)
            {
                if (j>i)
                {
                    swap(a[i][j], a[j][i]);
                }
            }
        }
        swap(n, m);
        swap(r, c);
    }

    for (i=1;i<=n;++i)
        for (j=1;j<=m;++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=c+1;j<=m;++j)
            st+=b[j];

        if (st>stmax) stmax=st;
    }

    g<<stmax<<"\n";

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

    return 0;
}