Cod sursa(job #644159)

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

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

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]);
for(i=1;i<=(1<<m);i++)
     s[i]=1;
for(i=1;i<(1<<m);i++)
     {if(2*i<=(1<<m)) 
             s[2*i]=s[i];
     if(2*i+1<=(1<<m)) 
             s[2*i+1]=s[i]+1;}
if(r<=c)
     if(r)
            {for(k=1;k<=(1<<n);k++)
            if(s[k]==r)
                    {for(i=0,v=1;i<n;i++,v<<=1)
                    if(k&v)
                            l[i+1]=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
            {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];}}
else
     if(c)
            {for(k=1;k<=(1<<m);k++)
            if(s[k]==c)
                    {for(i=0,v=1;i<m;i++,v<<=1)
                    if(k&v)
                            l[i+1]=1;
                    for(j=1;j<=n;j++)
                            q[j]=0;
                    for(i=1,d=0;i<=m;i++)
                    if(!l[i])
                            for(j=1;j<=n;j++)
                                   q[j]+=a[j][i],d+=a[j][i];
                    else
                            l[i]=0;
                    sort(q+1,q+n+1,cmp);
                    for(j=1;j<=r;j++)
                            d-=q[j];
                    if(d>u)
                            u=d;}}
     else
            if(r)
                    {for(i=1;i<=n;i++)
                            q[i]=0;
                    for(i=1,u=0;i<=m;i++)
                    for(j=1;j<=n;j++)
                            q[j]+=a[j][i],u+=a[j][i];
                    sort(q+1,q+n+1,cmp);
                    for(j=1;j<=r;j++)
                            u-=q[j];}
fprintf(g,"%d",u);
return 0;}