Cod sursa(job #7243)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 21 ianuarie 2007 13:13:42
Problema Elimin Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 3.16 kb
#include <stdio.h>
#include <string.h>

#define AMAX 7300

int n,m,l,c,i,j,LL[AMAX],CC[AMAX];
long L[AMAX], C[AMAX];
long long S=0,SS=0;

void Qsort_L(long li, long ls)
{
 long i=li, j=ls, x = L[(li+ls)/2], y;
 while (i<=j)
      {
       while (L[i]<x) i++;
       while (L[j]>x) j--;
       if (i<=j)
         {
          y=L[i]; L[i]=L[j]; L[j]=y;
          y=LL[i]; LL[i]=LL[j]; LL[j]=y;
          i++; j--;
         }
      }
 if (i<ls) Qsort_L(i,ls);
 if (li<j) Qsort_L(li,j);
}

void Qsort_C(long li, long ls)
{
 long i=li, j=ls, x = C[(li+ls)/2], y;
 while (i<=j)
      {
       while (C[i]<x) i++;
       while (C[j]>x) j--;
       if (i<=j)
         {
          y=C[i]; C[i]=C[j]; C[j]=y;
          y=CC[i]; CC[i]=CC[j]; CC[j]=y;
          i++; j--;
         }
      }
 if (i<ls) Qsort_C(i,ls);
 if (li<j) Qsort_C(li,j);
}

int LIN_BUN(int x)
{
 int gasit=0,i;
 for (i=1;i<=l;i++)
    if (LL[i]==x)
      { gasit=1; break; }
 return gasit;
}

int COL_BUN(int x)
{
 int gasit=0,i;
 for (i=1;i<=c;i++)
    if (CC[i]==x)
      { gasit=1; break;}
 return gasit;
}

int main()
{
 FILE* f = fopen("elimin.in","r");

 fscanf(f,"%d%d%d%d",&n,&m,&l,&c);

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    {
     long x;
     fscanf(f,"%ld",&x);
     L[i]+=x;
     C[j]+=x;
     S+=x;
    }
 for (i=1;i<=n;i++)
    LL[i]=i;
 for (i=1;i<=m;i++)
    CC[i]=i;

 fclose(f);

 // Mai inatai sortez linii si apoi coloanele

 f = fopen("elimin.in","r");

 fscanf(f,"%d%d%d%d",&n,&m,&l,&c);
 
 S=0;
 Qsort_L(1,n);
 
 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    {
     long x;
     fscanf(f,"%ld",&x);
     if (LIN_BUN(i))
       {
        C[j]-=x;
        S+=x;
       }
    }
 Qsort_C(1,m);

 fclose(f);
 f = fopen("elimin.in","r");
 fscanf(f,"%d%d%d%d",&n,&m,&l,&c);

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    {
     long x;
     fscanf(f,"%ld",&x);
     if (COL_BUN(j))
       {
        L[i]-=x;
        S+=x;
       }
    }
 S=0;
 for (i=1;i<=m;i++)
    if (!COL_BUN(CC[i]))
      S+=C[i];


 fclose(f);


 f = fopen("elimin.in","r");

 fscanf(f,"%d%d%d%d",&n,&m,&l,&c);

 memset(L,0,sizeof(L));
 memset(C,0,sizeof(C));

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    {
     long x;
     fscanf(f,"%ld",&x);
     L[i]+=x;
     C[j]+=x;
     SS+=x;
    }
 for (i=1;i<=n;i++)
    LL[i]=i;
 for (i=1;i<=m;i++)
    CC[i]=i;

 fclose(f);
 

 // Mai intai sortez coloanele si apoi liniile

 f = fopen("elimin.in","r");

 fscanf(f,"%d%d%d%d",&n,&m,&l,&c);

 Qsort_C(1,m);

 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    {
     long x;
     fscanf(f,"%ld",&x);
     if (COL_BUN(j))
       {
        L[i]-=x;
       }
    }
 fclose(f);
 f = fopen("elimin.in","r");

 fscanf(f,"%d%d%d%d",&n,&m,&l,&c);

 Qsort_L(1,n);
 
 for (i=1;i<=n;i++)
 for (j=1;j<=m;j++)
    {
     long x;
     fscanf(f,"%ld",&x);
     if (LIN_BUN(i))
       {
        C[j]-=x;
       }
    }
 SS=0;
 for (i=1;i<=n;i++)
    if (!LIN_BUN(LL[i]))
      SS+=L[i];

 if (SS>S)
   S=SS;

 fclose(f);

 freopen("elimin.out","w",stdout);
 printf("%lld",S);
 fclose(stdout);
 
 return 0;
}