Cod sursa(job #1867043)

Utilizator hrazvanHarsan Razvan hrazvan Data 3 februarie 2017 18:01:36
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <algorithm>
#define MAXN 50000
#define MAXK 50000
#define MAXT 1000
typedef struct{
  int p, t;
}pr;
pr v[MAXN];
int heap[MAXK], dh = 0;
int smax[MAXT];
int d[MAXK + 1];

bool cmp(pr a, pr b){
  if(a.t < b.t)
    return 1;
  return 0;
}

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

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

inline void cobor(int x){
  int best = x;
  do{
    x = best;
    if(heap[best] > heap[2 * x + 1])
      best = 2 * x + 1;
    if(2 * x + 2 < dh && heap[best] > heap[2 * x + 2])
      best = 2 * x + 2;
    intersch(x, best);
  }while(2 * best + 1 < dh && best != x);
}

int main(){
  FILE *in = fopen("peste.in", "r");
  int k, n, t, i, j, sum = 0, rez = 0, tmax;
  fscanf(in, "%d%d%d", &k, &n, &t);
  for(i = 0; i < n; i++)
    fscanf(in, "%d%d", &v[i].p, &v[i].t);
  fclose(in);
  std::sort(v, v + n, cmp);
  for(i = 0; i < n; i++){
    if(dh < k){
      sum += v[i].p;
      heap[dh] = v[i].p;
      urc(dh);
      dh++;
    }
    else{
      if(heap[0] < v[i].p){
        sum -= heap[0];
        heap[0] = v[i].p;
        cobor(0);
      }
    }
    smax[v[i].t] = sum;
  }
  tmax = v[n - 1].t;
  for(i = 1; i <= t; i++)
    for(j = 1; j <= i && j <= tmax; j++)
      if(d[i] < d[i - j] + smax[j])
        d[i] = d[i - j] + smax[j];
  FILE *out = fopen("peste.out", "w");
  fprintf(out, "%d", d[t]);
  fclose(out);
  return 0;
}