제출 #569921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569921		SSRS	Fireworks (APIO16_fireworks)	C++14	100 / 100	422 ms	64876 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
int main(){
  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];
    P[i]--;
  }
  vector<vector<int>> c(N + M);
  for (int i = 1; i < N + M; i++){
    c[P[i]].push_back(i);
  }
  vector<long long> mn(N + M, 0);
  vector<priority_queue<long long>> L(N + M);
  vector<priority_queue<long long, vector<long long>, greater<long long>>> R(N + M);
  for (int i = N; i < N + M; i++){
    L[i].push(0);
    R[i].push(0);
  }
  for (int i = N - 1; i >= 0; i--){
    for (int j : c[i]){
      long long x = L[j].top();
      L[j].pop();
      L[j].push(x + C[j]);
      long long y = R[j].top();
      while (!R[j].empty()){
        R[j].pop();
      }
      R[j].push(y + C[j]);
    }
    for (int j : c[i]){
      if (L[j].size() + R[j].size() > L[i].size() + R[i].size()){
        swap(mn[i], mn[j]);
        swap(L[i], L[j]);
        swap(R[i], R[j]);
      }
      mn[i] += mn[j];
      while (!R[j].empty()){
        long long a = R[j].top();
        R[j].pop();
        if (!L[i].empty()){
          mn[i] += max(L[i].top() - a, (long long) 0);
        }
        L[i].push(a);
        R[i].push(L[i].top());
        L[i].pop();
      }
      while (!L[j].empty()){
        long long a = L[j].top();
        L[j].pop();
        if (!R[i].empty()){
          mn[i] += max(a - R[i].top(), (long long) 0);
        }
        R[i].push(a);
        L[i].push(R[i].top());
        R[i].pop();
      }
    }
  }
  cout << mn[0] << endl;
}

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