# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
398727 | 2021-05-04T18:49:54 Z | ChrisT | Worst Reporter 4 (JOI21_worst_reporter4) | C++17 | 231 ms | 201444 KB |
#include <bits/stdc++.h> using namespace std; const int MN = 2e5 + 5, SUB = 5e3 + 1; int a[MN], h[MN], c[MN]; long long dp[SUB][SUB]; vector<int> adj[MN], xs; int getx (int x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;} void dfs (int cur) { for (int i : adj[cur]) { dfs(i); for (int j = 1; j <= (int)xs.size(); j++) dp[cur][j] += dp[i][j]; } for (int j = 1; j <= (int)xs.size(); j++) dp[cur][j] += c[cur]; dp[cur][h[cur]] -= c[cur]; for (int j = (int)xs.size()-1; j >= 1; j--) dp[cur][j] = min(dp[cur][j],dp[cur][j+1]); } int main () { int n; scanf ("%d",&n); for (int i = 1; i <= n; i++) { scanf ("%d %d %d",&a[i],&h[i],&c[i]); xs.push_back(h[i]); if (i > 1) adj[a[i]].push_back(i); } sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); for (int i = 1; i <= n; i++) h[i] = getx(h[i]); dfs(1); long long ret = 1e18; for (int i = 1; i <= (int)xs.size(); i++) ret = min(ret,dp[1][i]); printf ("%lld\n",ret); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 3 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 5008 KB | Output is correct |
4 | Correct | 3 ms | 4940 KB | Output is correct |
5 | Correct | 219 ms | 200912 KB | Output is correct |
6 | Correct | 19 ms | 29516 KB | Output is correct |
7 | Correct | 15 ms | 25960 KB | Output is correct |
8 | Correct | 220 ms | 200932 KB | Output is correct |
9 | Correct | 20 ms | 29508 KB | Output is correct |
10 | Correct | 15 ms | 25932 KB | Output is correct |
11 | Correct | 14 ms | 25676 KB | Output is correct |
12 | Correct | 218 ms | 201444 KB | Output is correct |
13 | Correct | 18 ms | 26444 KB | Output is correct |
14 | Correct | 229 ms | 201328 KB | Output is correct |
15 | Correct | 19 ms | 29740 KB | Output is correct |
16 | Correct | 231 ms | 201028 KB | Output is correct |
17 | Correct | 18 ms | 29516 KB | Output is correct |
18 | Correct | 14 ms | 25676 KB | Output is correct |
19 | Correct | 225 ms | 201116 KB | Output is correct |
20 | Correct | 18 ms | 29752 KB | Output is correct |
21 | Correct | 14 ms | 25932 KB | Output is correct |
22 | Correct | 214 ms | 200848 KB | Output is correct |
23 | Correct | 19 ms | 29516 KB | Output is correct |
24 | Correct | 217 ms | 201132 KB | Output is correct |
25 | Correct | 20 ms | 29636 KB | Output is correct |
26 | Correct | 218 ms | 201432 KB | Output is correct |
27 | Correct | 222 ms | 201128 KB | Output is correct |
28 | Correct | 218 ms | 201168 KB | Output is correct |
29 | Correct | 218 ms | 201284 KB | Output is correct |
30 | Correct | 227 ms | 201176 KB | Output is correct |
31 | Correct | 219 ms | 201244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 219 ms | 200972 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 3 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 5008 KB | Output is correct |
4 | Correct | 3 ms | 4940 KB | Output is correct |
5 | Correct | 219 ms | 200912 KB | Output is correct |
6 | Correct | 19 ms | 29516 KB | Output is correct |
7 | Correct | 15 ms | 25960 KB | Output is correct |
8 | Correct | 220 ms | 200932 KB | Output is correct |
9 | Correct | 20 ms | 29508 KB | Output is correct |
10 | Correct | 15 ms | 25932 KB | Output is correct |
11 | Correct | 14 ms | 25676 KB | Output is correct |
12 | Correct | 218 ms | 201444 KB | Output is correct |
13 | Correct | 18 ms | 26444 KB | Output is correct |
14 | Correct | 229 ms | 201328 KB | Output is correct |
15 | Correct | 19 ms | 29740 KB | Output is correct |
16 | Correct | 231 ms | 201028 KB | Output is correct |
17 | Correct | 18 ms | 29516 KB | Output is correct |
18 | Correct | 14 ms | 25676 KB | Output is correct |
19 | Correct | 225 ms | 201116 KB | Output is correct |
20 | Correct | 18 ms | 29752 KB | Output is correct |
21 | Correct | 14 ms | 25932 KB | Output is correct |
22 | Correct | 214 ms | 200848 KB | Output is correct |
23 | Correct | 19 ms | 29516 KB | Output is correct |
24 | Correct | 217 ms | 201132 KB | Output is correct |
25 | Correct | 20 ms | 29636 KB | Output is correct |
26 | Correct | 218 ms | 201432 KB | Output is correct |
27 | Correct | 222 ms | 201128 KB | Output is correct |
28 | Correct | 218 ms | 201168 KB | Output is correct |
29 | Correct | 218 ms | 201284 KB | Output is correct |
30 | Correct | 227 ms | 201176 KB | Output is correct |
31 | Correct | 219 ms | 201244 KB | Output is correct |
32 | Incorrect | 219 ms | 200972 KB | Output isn't correct |
33 | Halted | 0 ms | 0 KB | - |