Cod sursa(job #1535819)

Utilizator hrazvanHarsan Razvan hrazvan Data 25 noiembrie 2015 10:58:29
Problema Fabrica Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#define MAXN 100000
#define MAXNR 50000
int v[MAXNR], reza[MAXN], rezb[MAXN];
int h[MAXNR], hp[MAXNR], dr;

inline void intersch(int x, int y){
  int aux;
  aux = h[x];  h[x] = h[y];  h[y] = aux;
  aux = hp[x];  hp[x] = hp[y];  hp[y] = aux;
}

inline void cobor(int x){
  int best;
  char g = 1;
  while(2 * x + 1 < dr && g){
    best = 2 * x + 1;
    if(2 * x + 2 < dr && h[best] > h[2 * x + 2])
      best = 2 * x + 2;
    if(h[x] > h[best]){
      intersch(x, best);
      x = best;
    }
    else
      g = 0;
  }
}

inline void urc(int x){
  while(x > 0 && h[(x - 1) / 2] > h[x]){
    intersch((x - 1) / 2, x);
    x = (x - 1) / 2;
  }
}

inline void scot(int *x, int *y){
  *x = h[0];
  *y = hp[0];
  intersch(0, dr - 1);
  dr--;
  cobor(0);
}

inline void add(int x, int y){
  h[dr] = x;
  hp[dr] = y;
  urc(dr);
  dr++;
}

inline void calc(int n, int x, int *rez){
  dr = 0;
  int i, aux;
  for(i = 0; i < x; i++)
    add(v[i], i);
  for(i = 0; i < n; i++){
    scot(&rez[i], &aux);
    add(rez[i] + v[aux], aux);
  }
}

int main(){
  FILE *in = fopen("fabrica.in", "r");
  int n, a, b, i;
  fscanf(in, "%d%d%d", &n, &a, &b);
  for(i = 0; i < a; i++)
    fscanf(in, "%d", &v[i]);
  calc(n, a, reza);
  for(i = 0; i < b; i++)
    fscanf(in, "%d", &v[i]);
  calc(n, b, rezb);
  fclose(in);
  FILE *out = fopen("fabrica.out", "w");
  int max = 0;
  fprintf(out, "%d ", a);
  for(i = 0; i < n; i++)
    if(max < reza[i] + rezb[n - i - 1])
      max = reza[i] + rezb[n - i - 1];
  fprintf(out, "%d", max);
  fclose(out);
  return 0;
}