Submission #1256722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256722		LucaLucaM	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	368 ms	589824 KiB

worst_reporter2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

void merge(std::map<int, ll> &a, const std::map<int, ll> &b) {
  for (auto &[h, v] : a) {
    ll best = 0;
    for (const auto &[x, y] : b) {
      if (x <= h) {
        best = std::max(best, y);
      }
    }
    v += best;
  }
}

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::vector<int> h(n), c(n);
  std::vector<std::vector<int>> g(n);

  std::vector<int> norm;

  ll answer = 0;
  for (int i = 0; i < n; i++) {
    int p;
    std::cin >> p >> h[i] >> c[i];
    norm.push_back(h[i]);
    p--;
    answer += c[i];
    if (p != i) {
      g[p].push_back(i);
    }
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());
  
  for (int &x : h) {
    x = std::lower_bound(norm.begin(), norm.end(), x) - norm.begin() + 1;
  }

  std::vector<std::vector<ll>> delta(n, std::vector<ll>(n + 1, 0));

  auto dfs = [&](auto &&self, int u) -> void {
    for (int v : g[u]) {
      self(self, v);
    }

    for (int v : g[u]) {
      for (int i = 1; i <= n; i++) {
        delta[u][i] += delta[v][i];
      } 
    }

    delta[u][h[u]] += c[u];
    ll val = c[u];
    for (int i = h[u] - 1; i > 0 && val; i--) {
      ll take = std::min(val, delta[u][i]);
      delta[u][i] -= take;
      val -= take;
    }
  };

  dfs(dfs, 0);

  for (int j = 1; j <= n; j++) {
    answer -= delta[0][j];
  }
  
  std::cout << answer;
  
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21