제출 #241487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241487		rama_pang	Fireworks (APIO16_fireworks)	C++14	100 / 100	221 ms	44136 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

struct Node {
  long long m = 0, c = 0;
  priority_queue<long long> pq;

  void Merge(Node &o) {
    m += o.m;
    c += o.c;
    if (pq.size() < o.pq.size()) {
      swap(pq, o.pq);
    }
    while (!o.pq.empty()) {
      pq.emplace(o.pq.top());
      o.pq.pop();
    }
  }

  void Process(long long C) {
    while (m > 1) {
      m--;
      c += pq.top();
      pq.pop();
    }
    long long u = pq.top(); pq.pop();
    long long v = pq.top(); pq.pop();
    c -= C;
    pq.emplace(v + C);
    pq.emplace(u + C);
  }

  long long Evaluate() {
    return m * pq.top() + c;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  vector<int> P(N + M), C(N + M);
  for (int i = 1; i < N + M; i++) {
    cin >> P[i] >> C[i];
  }

  vector<Node> node(N + M);
  for (int i = N + M - 1; i >= 0; i--) {
    if (i >= N) {
      node[i].m = 1;
      node[i].c = -C[i];
      node[i].pq.emplace(C[i]);
      node[i].pq.emplace(C[i]);
    } else {
      node[i].Process(C[i]);
    }
    if (i > 0) {
      node[--P[i]].Merge(node[i]);
    }
  }

  cout << node[0].Evaluate() << "\n";
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45