# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
518919 | ParsaAlizadeh | Worst Reporter 4 (JOI21_worst_reporter4) | C++17 | 191 ms | 118200 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) begin(x), end(x)
#define kill(x) return cout << x << '\n', 0
#define fst first
#define snd second
void assume(int expr) {
if (!expr) __builtin_unreachable();
}
constexpr int N = 5e3 + 10;
int n;
ll H[N], C[N], dp[N][N];
vector<int> adj[N];
void dfs(int u) {
static vector<int> st = {0};
st.push_back(u);
for (int v : adj[u])
dfs(v);
for (int j = 0; j+1 < st.size(); j++) {
dp[u][j] = C[u];
for (int v : adj[u])
dp[u][j] += dp[v][j];
if (H[u] >= H[st[j]]) {
ll tmp = 0;
for (int v : adj[u])
tmp += dp[v][st.size()-1];
dp[u][j] = min(dp[u][j], tmp);
}
// cout << u << ' ' << j << ' ' << st[j] << ' ' << dp[u][j] << endl;
}
st.pop_back();
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
assert(n < N);
for (int i = 1; i <= n; i++) {
int par;
cin >> par >> H[i] >> C[i];
if (i > 1)
adj[par].push_back(i);
}
dfs(1);
cout << dp[1][0] << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |