Cod sursa(job #642507)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 1 decembrie 2011 16:06:55
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<stdio.h>
#define N 1000
long n,m,i,j,a[N][N],r,c,k,x,s[N],t[N],o[N],d,u,b[N][N],y[N],z[N];
char w[10000];

void merge(long t[N],long y[N],long p,long q)
{long i,j,k,m=(p+q)/2;
if(p==q)
       return;
merge(t,y,p,m);
merge(t,y,m+1,q);
for(i=k=p,j=m+1;i<=m||j<=q;)
if(j>q||(i<=m&&t[i]<t[j]))
       z[k]=y[i],o[k++]=t[i++];
else
       z[k]=y[j],o[k++]=t[j++];
for(i=p;i<=q;i++)
       t[i]=o[i],y[i]=z[i];}

int main()
{FILE *f=fopen("elimin.in","r"),*g=fopen("elimin.out","w");
fscanf(f,"%ld%ld%ld%ld\n",&n,&m,&r,&c);
if(n>m)
     {for(i=1;i<=n;i++)
            {fgets(w,N,f);
            for(k=0,j=1;w[k]!='\n';k++)
            if(w[k]==' ')
                   j++;
            else
                   a[j][i]=a[j][i]*10+(w[k]-'0');}
     x=n,n=m,m=x,x=r,r=c,c=x;}
else
     for(i=1;i<=n;i++)
            {fgets(w,N,f);
            for(k=0,j=1;w[k]!='\n';k++)
            if(w[k]==' ')
                   j++;
            else
                   a[i][j]=a[i][j]*10+(w[k]-'0');}
for(i=1;i<=n;i++)
     {for(j=1;j<=m;j++)
            printf("%d ",a[i][j]);
     printf("\n");}
for(k=1;k;)
     {s[k]++;
     if(s[k]<=n-r+k)
             if(k==r)
                     {for(i=1;i<=n;i++)
                     for(j=1;j<=m;j++)
                            b[i][j]=a[i][j];
                     for(i=1;i<=r;i++)
                     for(j=1;j<=m;j++)
                            b[s[i]][j]=0;
                     for(i=1;i<=m;i++)
                            {t[i]=0,y[i]=i;
                            for(j=1;j<=n;j++)
                                    t[i]+=b[j][i];}
                     merge(t,y,1,m),d=0;
                     for(j=1;j<=c;j++)
                     for(i=1;i<=n;i++)
                            b[i][y[j]]=0;
                     for(i=1;i<=n;i++)
                     for(j=1;j<=m;j++)
                            d+=b[i][j];
                     if(d>u)
                            u=d;}
             else
                     k++,s[k]=s[k-1];
     else
             k--;}
fprintf(g,"%ld",u);
return 0;}