Cod sursa(job #748149)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 12 mai 2012 16:12:48
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,m,r,c,i,j,v[1000][100],a[200],sumx=0,lin[1000];

void solve()
{
    int sum[1000],i,j;
    for (i=1;i<=m;i++) sum[i]=lin[i];
    for (i=1;i<=c;i++)
        for (j=1;j<=m;j++)
            sum[j]-=v[j][a[i]];
    sort(sum+1,sum+m+1);
    int s=0;
    for (i=r+1;i<=m;i++)
        s+=sum[i];
    sumx=max(s,sumx);
}
void bkt(int l)
{
    int i;
    if (l<=c)
    {
        for (i=a[l-1]+1;i<=n-c+l;i++)
        {
            a[l]=i;
            bkt(l+1);
        }
    }
    else
        solve();
}

int main ()
{
    int i,j;
    in>>m>>n>>r>>c;
    if (m<n)
    {
        for (i=1;i<=m;i++)
            for (j=1;j<=n;j++)
                in>>v[j][m-i+1];
        swap(m,n);
        swap(r,c);
    }
    else
    {
        for(i=1;i<=m;i++)
            for(j=1;j<=n;j++)
                    in>>v[i][j];
    }
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
        {
            lin[i]+=v[i][j];
        }
    bkt(1);
    out<<sumx<<'\n';
    return 0;
}