Cod sursa(job #644088)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 5 decembrie 2011 10:54:39
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.2 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 5000
typedef struct pe
{int y,t;};
pe q[N];
int n,m,i,j,a[20][N],r,c,k,x,s[N],d,u,l[N],w[N];

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

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