oj.uz

Submission #722476

# Submission time Handle Problem Language Result Execution time Memory
722476 2023-04-12T05:09:06 Z Abrar_Al_Samit Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 787 ms 197192 KB 
#include<bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
const int nax = 5003;
long long val[nax], cost[nax];
vector<int>g[nax];
int n;
bool root[nax];

long long dp[nax][nax];

long long solve(int v, int prv) {
	long long &ret = dp[v][prv];
	if(ret!=-1) return ret;
	ret = INF;
	if(!prv || val[v]>=val[prv]) {
		ret = 0;
		for(int u : g[v]) {
			ret += solve(u, v);
		}
	}
	long long an = cost[v];
	for(int u : g[v]) {
		an += solve(u, prv);
	}
	ret = min(ret, an);
	return ret;
}
void PlayGround() {
	cin>>n;

	for(int i=1; i<=n; ++i) root[i] = 1;
	for(int i=1; i<=n; ++i) {
		int to;
		cin>>to>>val[i]>>cost[i];

		if(to-i) g[to].push_back(i), root[i] = 0;
	}

	long long ans = 0;
	memset(dp, -1, sizeof dp);
	for(int i=1; i<=n; ++i) if(root[i]) {
		ans += solve(i, 0);
	}
	cout<<ans<<'\n';

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 196332 KB Output is correct
2 Correct 79 ms 196296 KB Output is correct
3 Correct 78 ms 196380 KB Output is correct
4 Correct 73 ms 196264 KB Output is correct
5 Correct 76 ms 196652 KB Output is correct
6 Correct 77 ms 196632 KB Output is correct
7 Correct 85 ms 196616 KB Output is correct
8 Correct 81 ms 196584 KB Output is correct
9 Correct 80 ms 196556 KB Output is correct
10 Correct 79 ms 196640 KB Output is correct
11 Correct 81 ms 196632 KB Output is correct
12 Correct 787 ms 197192 KB Output is correct
13 Correct 757 ms 197176 KB Output is correct
14 Correct 407 ms 196900 KB Output is correct
15 Correct 344 ms 196936 KB Output is correct
16 Correct 82 ms 196560 KB Output is correct
17 Correct 91 ms 196568 KB Output is correct
18 Correct 77 ms 196548 KB Output is correct
19 Correct 360 ms 196864 KB Output is correct
20 Correct 460 ms 196760 KB Output is correct
21 Correct 403 ms 196948 KB Output is correct
22 Correct 82 ms 196508 KB Output is correct
23 Correct 83 ms 196584 KB Output is correct
24 Correct 512 ms 196892 KB Output is correct
25 Correct 462 ms 196888 KB Output is correct
26 Correct 322 ms 197188 KB Output is correct
27 Correct 205 ms 196796 KB Output is correct
28 Correct 333 ms 196920 KB Output is correct
29 Correct 464 ms 197032 KB Output is correct
30 Correct 356 ms 196924 KB Output is correct
31 Correct 344 ms 196960 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 196332 KB Output is correct
2 Correct 79 ms 196296 KB Output is correct
3 Correct 78 ms 196380 KB Output is correct
4 Correct 73 ms 196264 KB Output is correct
5 Correct 76 ms 196652 KB Output is correct
6 Correct 77 ms 196632 KB Output is correct
7 Correct 85 ms 196616 KB Output is correct
8 Correct 81 ms 196584 KB Output is correct
9 Correct 80 ms 196556 KB Output is correct
10 Correct 79 ms 196640 KB Output is correct
11 Correct 81 ms 196632 KB Output is correct
12 Correct 787 ms 197192 KB Output is correct
13 Correct 757 ms 197176 KB Output is correct
14 Correct 407 ms 196900 KB Output is correct
15 Correct 344 ms 196936 KB Output is correct
16 Correct 82 ms 196560 KB Output is correct
17 Correct 91 ms 196568 KB Output is correct
18 Correct 77 ms 196548 KB Output is correct
19 Correct 360 ms 196864 KB Output is correct
20 Correct 460 ms 196760 KB Output is correct
21 Correct 403 ms 196948 KB Output is correct
22 Correct 82 ms 196508 KB Output is correct
23 Correct 83 ms 196584 KB Output is correct
24 Correct 512 ms 196892 KB Output is correct
25 Correct 462 ms 196888 KB Output is correct
26 Correct 322 ms 197188 KB Output is correct
27 Correct 205 ms 196796 KB Output is correct
28 Correct 333 ms 196920 KB Output is correct
29 Correct 464 ms 197032 KB Output is correct
30 Correct 356 ms 196924 KB Output is correct
31 Correct 344 ms 196960 KB Output is correct
32 Correct 85 ms 196604 KB Output is correct
33 Runtime error 4 ms 848 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 70 ms 196332 KB Output is correct
2 Correct 79 ms 196296 KB Output is correct
3 Correct 78 ms 196380 KB Output is correct
4 Correct 73 ms 196264 KB Output is correct
5 Correct 76 ms 196652 KB Output is correct
6 Correct 77 ms 196632 KB Output is correct
7 Correct 85 ms 196616 KB Output is correct
8 Correct 81 ms 196584 KB Output is correct
9 Correct 80 ms 196556 KB Output is correct
10 Correct 79 ms 196640 KB Output is correct
11 Correct 81 ms 196632 KB Output is correct
12 Correct 787 ms 197192 KB Output is correct
13 Correct 757 ms 197176 KB Output is correct
14 Correct 407 ms 196900 KB Output is correct
15 Correct 344 ms 196936 KB Output is correct
16 Correct 82 ms 196560 KB Output is correct
17 Correct 91 ms 196568 KB Output is correct
18 Correct 77 ms 196548 KB Output is correct
19 Correct 360 ms 196864 KB Output is correct
20 Correct 460 ms 196760 KB Output is correct
21 Correct 403 ms 196948 KB Output is correct
22 Correct 82 ms 196508 KB Output is correct
23 Correct 83 ms 196584 KB Output is correct
24 Correct 512 ms 196892 KB Output is correct
25 Correct 462 ms 196888 KB Output is correct
26 Correct 322 ms 197188 KB Output is correct
27 Correct 205 ms 196796 KB Output is correct
28 Correct 333 ms 196920 KB Output is correct
29 Correct 464 ms 197032 KB Output is correct
30 Correct 356 ms 196924 KB Output is correct
31 Correct 344 ms 196960 KB Output is correct
32 Correct 85 ms 196604 KB Output is correct
33 Runtime error 4 ms 848 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -