Submission #969509

#	Time	Username	Problem	Language	Result	Execution time	Memory
969509		kilkuwu	Fireworks (APIO16_fireworks)	C++17	19 / 100	16 ms	1368 KiB

fireworks

#include <bits/stdc++.h>

#define nl '\n'

#define int int64_t

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n, m;
  std::cin >> n >> m;
  const int inf = 1e9 + 7;
  std::vector<int> pa(n + m), co(n + m);

  std::vector<std::vector<std::pair<int, int>>> adj(n + m);

  for (int i = 1; i < n + m; i++) {
    std::cin >> pa[i] >> co[i];
    adj[--pa[i]].emplace_back(i, co[i]);
  }

  std::vector<std::vector<int>> dp(n + m, std::vector<int>(301));

  auto dfs = [&](auto self, int u, int p) -> void {
    if (adj[u].size() == 0) {
      dp[u][0] = 0;
      for (int i = 1; i <= 300; i++) {
        dp[u][i] = inf;
      }
      return;
    }

    for (auto [v, c] : adj[u]) {
      self(self, v, u);
    }


    for (int j = 0; j <= 300; j++) {
      dp[u][j] = 0;
      for (auto [v, c] : adj[u]) {
        int minimal = inf;
        for (int k = 0; k <= j; k++) {
          minimal = std::min(minimal, dp[v][k] + std::abs(j - k - c));
        }
        dp[u][j] += minimal;
      }
      dp[u][j] = std::min(dp[u][j], inf);
    }
  };

  dfs(dfs, 0, 0);

  std::cout << *std::min_element(dp[0].begin(), dp[0].end()) << nl;
}

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