Cod sursa(job #7311)

Utilizator raula_sanChis Raoul raula_san Data 21 ianuarie 2007 13:24:32
Problema Elimin Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 2.65 kb
#include<cstdio>
#define dim 7300

int N, M, R, C, ri[dim];

long r[dim], c[dim], S;

void read()
{
     freopen("elimin.in", "r", stdin);
     
     scanf("%d %d %d %d", &N, &M, &R, &C);
 
     int i, j, NR;
     
     for(i=1; i<=N; ++i)
              for(j=1; j<=M; ++j)
              {
                       scanf("%d", &NR);
                       r[i] += NR;
                       ri[i] = i;
                       
                       S += NR;
              }
}

void swap(long h[], int hi[], int i, int j)
{
     h[i] ^= h[j] ^= h[i] ^= h[j];
     hi[i] ^= hi[j] ^= hi[i] ^= hi[j];
}

void heapup(long h[], int hi[], int k)
{
	 if(k <= 1)
		return;

     int t = k / 2;
     
     if(h[t] < h[k])
     {
             swap(h, hi, k, t);
             heapup(h, hi, t);
     }
}

void buildh(long h[], int hi[], int N)
{
     int i;
     
     for(i=2; i<=N; ++i)
              heapup(h, hi, i);
}

void restore(long h[], int hi[], int r, int b)
{
     if((r << 1) <= b)
     {
           long st, dr, poz;
           
           st = h[r << 1];
           
           if(((r << 1) + 1) <= b)
                  dr = h[(r << 1) + 1];
           else
               dr = st - 1;
               
           poz = st > dr ? r << 1 : (r << 1) + 1;
           
           if(h[r] < h[poz])
           {
                   swap(h, hi, r, poz);
                   restore(h, hi, poz, b);
           }
     }
}

void heapsort(long h[], int hi[], int N)
{
     int i;
     
     for(i=N; i>1; --i)
     {
              swap(h, hi, 1, i);
              restore(h, hi, 1, i-1);
     }
}

int exist(int l)
{
    int i;
    
    for(i=1; i<=R; ++i)
             if(ri[i] == l)
                      return 1;
                      
    return 0;
}

void greedy()
{
     int i, j, NR;
     
     for(i=1; i<=R; ++i)
              S -= r[i];
              
     fclose(stdin);
     
     freopen("elimin.in", "r", stdin);
     
     scanf("%d %d %d %d", &N, &M, &R, &C);
     
     for(i=1; i<=N; ++i)
              for(j=1; j<=M; ++j)
              {
                       scanf("%d", &NR);
                         
                       if(!exist(i))
                                    c[j] += NR;
              }
              
     buildh(c, ri, N); heapsort(c, ri, N);
     
     for(i=1; i<=C; ++i)
              S -= c[i];
}

void write()
{
     freopen("elimin.out", "w", stdout);
     
     printf("%ld", S);
}

int main()
{     
    read();
    buildh(r, ri, N); heapsort(r, ri, N);
    greedy();
    write();
    
    fclose(stdin); fclose(stdout);
    return 0;
}