Cod sursa(job #1068770)

Utilizator Teodor94Teodor Plop Teodor94 Data 28 decembrie 2013 18:47:13
Problema Elimin Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.19 kb
#include<cstdio>
#include<string>
#include<algorithm>
 
using namespace std;
 
const int N=555;
const int M=20;
 
int a[N][N],n,m,r,c,sol[M],s[N],s2[N],best;
 
void read()
{
    scanf("%d%d%d%d",&n,&m,&r,&c);
    int i,j;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            scanf("%d",&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[i]+=a[i][j];
}
 
void solve()
{
    int i,j,sum=0;
    memcpy(s2,s,sizeof(s));
    for (i=1;i<=c;++i)
        for (j=1;j<=n;++j)
            s2[j]-=a[j][sol[i]];
    sort(s2+1,s2+n+1);
    for (i=r+1;i<=n;++i)
        sum+=s2[i];
    if (sum>best)
        best=sum;
}
 
void back(int k)
{
    if (k==c+1)
    {
        solve();
        return;
    }
    for (int i=sol[k-1]+1;i<=m;++i)
    {
        sol[k]=i;
        back(k+1);
    }
}
 
int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    read();
    back(1);
    printf("%d\n",best);
    return 0;
}