Cod sursa(job #644129)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 5 decembrie 2011 12:06:14
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 2000
int n,m,i,j,a[20][N],r,c,k,x,s[20],d,u,l[20],q[N];

int cmp(int a,int b)
{return a<b;}

void bkt(int k)
{int i,j;
if(k-1==r)
      {for(i=1;i<=r;i++)
            l[s[i]]=1;
      for(j=1;j<=m;j++)
            q[j]=0;
      for(i=1,d=0;i<=n;i++)
      if(!l[i])
            for(j=1;j<=m;j++)
                   q[j]+=a[i][j],d+=a[i][j];
      else
            l[i]=0;
      sort(q+1,q+m+1,cmp);
      for(j=1;j<=c;j++)
            d-=q[j];
      if(d>u)
            u=d;}
else
      for(i=s[i-1]+1;i<=n-r+k;i++)
            s[k]=i,bkt(k+1);}

int main()
{FILE *f=fopen("elimin.in","r"),*g=fopen("elimin.out","w");
fscanf(f,"%d%d%d%d",&n,&m,&r,&c);
if(n>m)
     {for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
            fscanf(f,"%d",&a[j][i]);
     x=n,n=m,m=x,x=r,r=c,c=x;}
else
     for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
            fscanf(f,"%d",&a[i][j]);
if(r)
     bkt(1);
else
     if(c)
            {for(i=1;i<=m;i++)
                   q[i]=0;
            for(i=1,u=0;i<=n;i++)
            for(j=1;j<=m;j++)
                   q[j]+=a[i][j],u+=a[i][j];
            sort(q+1,q+m+1,cmp);
            for(j=1;j<=c;j++)
                   u-=q[j];}
fprintf(g,"%d",u);
return 0;}