Cod sursa(job #631836)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 9 noiembrie 2011 20:35:08
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>
#define N 1000
int n,m,i,j,a[300][N],r,c,k,x,s[N],t[N],o[N],d,u,b[300][N],y[N],z[N];

void merge(int t[N],int y[N],int p,int q)
{int 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,&m,&r,&c);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
     fscanf(f,"%ld",&a[i][j]);
if(r>c)
     x=r,r=c,c=x,x=n,n=m,m=x;
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;}