oj.uz

Submission #417296

# Submission time Handle Problem Language Result Execution time Memory
417296 2021-06-03T14:32:28 Z pavement Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 903 ms 524288 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, sumC, A[200005], H[200005], C[200005], mem[5005][2][5005];
vector<int> adj[5005];

int dp(int n, bool b, int h = 0, int e = -1) {
	if (mem[n][b][h] != -1) return mem[n][b][h];
	int ans = (b ? C[n] : 0);
	for (auto u : adj[n]) if (u != e) {
		int ret = dp(u, 0, h, n);
		if (h == 0 || H[h] <= H[u]) ret = max(ret, dp(u, 1, u, n));
		ans += ret;
	}
	return mem[n][b][h] = ans;
}

main() {
	memset(mem, -1, sizeof mem);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> H[i] >> C[i];
		if (i != A[i])
			adj[A[i]].pb(i);
		sumC += C[i];
	}
	int x = max(dp(1, 0), dp(1, 1, 1));
	cout << sumC - x << '\n';
}

Compilation message

worst_reporter2.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main() {
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 392664 KB Output is correct
2 Correct 168 ms 392496 KB Output is correct
3 Correct 164 ms 392536 KB Output is correct
4 Correct 164 ms 392556 KB Output is correct
5 Correct 170 ms 392696 KB Output is correct
6 Correct 169 ms 392716 KB Output is correct
7 Correct 173 ms 392772 KB Output is correct
8 Correct 190 ms 392736 KB Output is correct
9 Correct 176 ms 392740 KB Output is correct
10 Correct 181 ms 392776 KB Output is correct
11 Correct 176 ms 392916 KB Output is correct
12 Correct 877 ms 393468 KB Output is correct
13 Correct 903 ms 393464 KB Output is correct
14 Correct 501 ms 393236 KB Output is correct
15 Correct 508 ms 393228 KB Output is correct
16 Correct 181 ms 392900 KB Output is correct
17 Correct 181 ms 392848 KB Output is correct
18 Correct 180 ms 392860 KB Output is correct
19 Correct 545 ms 393156 KB Output is correct
20 Correct 536 ms 393168 KB Output is correct
21 Correct 548 ms 393076 KB Output is correct
22 Correct 175 ms 392940 KB Output is correct
23 Correct 171 ms 392900 KB Output is correct
24 Correct 733 ms 393212 KB Output is correct
25 Correct 756 ms 393136 KB Output is correct
26 Correct 721 ms 393476 KB Output is correct
27 Correct 425 ms 393120 KB Output is correct
28 Correct 594 ms 393220 KB Output is correct
29 Correct 824 ms 393336 KB Output is correct
30 Correct 483 ms 393224 KB Output is correct
31 Correct 476 ms 393140 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 392664 KB Output is correct
2 Correct 168 ms 392496 KB Output is correct
3 Correct 164 ms 392536 KB Output is correct
4 Correct 164 ms 392556 KB Output is correct
5 Correct 170 ms 392696 KB Output is correct
6 Correct 169 ms 392716 KB Output is correct
7 Correct 173 ms 392772 KB Output is correct
8 Correct 190 ms 392736 KB Output is correct
9 Correct 176 ms 392740 KB Output is correct
10 Correct 181 ms 392776 KB Output is correct
11 Correct 176 ms 392916 KB Output is correct
12 Correct 877 ms 393468 KB Output is correct
13 Correct 903 ms 393464 KB Output is correct
14 Correct 501 ms 393236 KB Output is correct
15 Correct 508 ms 393228 KB Output is correct
16 Correct 181 ms 392900 KB Output is correct
17 Correct 181 ms 392848 KB Output is correct
18 Correct 180 ms 392860 KB Output is correct
19 Correct 545 ms 393156 KB Output is correct
20 Correct 536 ms 393168 KB Output is correct
21 Correct 548 ms 393076 KB Output is correct
22 Correct 175 ms 392940 KB Output is correct
23 Correct 171 ms 392900 KB Output is correct
24 Correct 733 ms 393212 KB Output is correct
25 Correct 756 ms 393136 KB Output is correct
26 Correct 721 ms 393476 KB Output is correct
27 Correct 425 ms 393120 KB Output is correct
28 Correct 594 ms 393220 KB Output is correct
29 Correct 824 ms 393336 KB Output is correct
30 Correct 483 ms 393224 KB Output is correct
31 Correct 476 ms 393140 KB Output is correct
32 Correct 178 ms 392916 KB Output is correct
33 Runtime error 643 ms 524288 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 392664 KB Output is correct
2 Correct 168 ms 392496 KB Output is correct
3 Correct 164 ms 392536 KB Output is correct
4 Correct 164 ms 392556 KB Output is correct
5 Correct 170 ms 392696 KB Output is correct
6 Correct 169 ms 392716 KB Output is correct
7 Correct 173 ms 392772 KB Output is correct
8 Correct 190 ms 392736 KB Output is correct
9 Correct 176 ms 392740 KB Output is correct
10 Correct 181 ms 392776 KB Output is correct
11 Correct 176 ms 392916 KB Output is correct
12 Correct 877 ms 393468 KB Output is correct
13 Correct 903 ms 393464 KB Output is correct
14 Correct 501 ms 393236 KB Output is correct
15 Correct 508 ms 393228 KB Output is correct
16 Correct 181 ms 392900 KB Output is correct
17 Correct 181 ms 392848 KB Output is correct
18 Correct 180 ms 392860 KB Output is correct
19 Correct 545 ms 393156 KB Output is correct
20 Correct 536 ms 393168 KB Output is correct
21 Correct 548 ms 393076 KB Output is correct
22 Correct 175 ms 392940 KB Output is correct
23 Correct 171 ms 392900 KB Output is correct
24 Correct 733 ms 393212 KB Output is correct
25 Correct 756 ms 393136 KB Output is correct
26 Correct 721 ms 393476 KB Output is correct
27 Correct 425 ms 393120 KB Output is correct
28 Correct 594 ms 393220 KB Output is correct
29 Correct 824 ms 393336 KB Output is correct
30 Correct 483 ms 393224 KB Output is correct
31 Correct 476 ms 393140 KB Output is correct
32 Correct 178 ms 392916 KB Output is correct
33 Runtime error 643 ms 524288 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -