Submission #681075

#	Time	Username	Problem	Language	Result	Execution time	Memory
681075		peijar	Magic Tree (CEOI19_magictree)	C++17	34 / 100	499 ms	1048576 KiB

magictree

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

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

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

  int nbSommet, nbFruits, nbJours;
  cin >> nbSommet >> nbFruits >> nbJours;
  vector<vector<int>> childs(nbSommet);

  for (int i = 1; i < nbSommet; ++i) {
    int p;
    cin >> p;
    childs[p - 1].push_back(i);
  }
  vector<pair<int, int>> fruits(nbSommet, pair(-1, -1));
  for (int i = 0; i < nbFruits; ++i) {
    int v, d, w;
    cin >> v >> d >> w;
    --v;
    fruits[v] = pair(d - 1, w);
  }
  vector<vector<int>> dp(nbSommet, vector<int>(nbJours));

  for (int u = nbSommet - 1; u >= 0; --u) {
    for (int v : childs[u])
      for (int d = 0; d < nbJours; ++d)
        dp[u][d] += dp[v][d];
    if (fruits[u] == pair<int, int>(-1, -1))
      continue;
    auto [d, w] = fruits[u];
    int x = dp[u][d] + w;
    for (int dd = d; dd < nbJours; ++dd)
      dp[u][dd] = max(dp[u][dd], x);
  }
  cout << dp[0].back() << endl;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17