oj.uz

Submission #417287

# Submission time Handle Problem Language Result Execution time Memory
417287 2021-06-03T14:25:10 Z shenxy Worst Reporter 4 (JOI21_worst_reporter4) C++11
14 / 100
 1296 ms 196932 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int N, A[5001], H[5001];
long long C[5001], dptable[5001][5001];
vector<int> adjlist[5001];
long long dp(int v, int k) {
	if (dptable[v][k] != -1) return dptable[v][k];
	if (H[v] >= H[k]) {
		long long a1 = 0, a2 = 0;
		if (H[v] != H[k]) a1 += C[v];
		for (int i: adjlist[v]) a1 += dp(i, k), a2 += dp(i, v);
		return dptable[v][k] = min(a1, a2);
	} else {
		dptable[v][k] = C[v];
		for (int i: adjlist[v]) dptable[v][k] += dp(i, k);
		return dptable[v][k];
	}
}
int main() {
	memset(dptable, -1, sizeof dptable);
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d %d %lld", &A[i], &H[i], &C[i]);
	for (int i = 2; i <= N; ++i) adjlist[A[i]].push_back(i);
	long long bans = 1000000000000000000LL;
	for (int i = 1; i <= N; ++i) bans = min(bans, dp(1, i));
	printf("%lld", bans);
	return 0;
}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:25:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  for (int i = 1; i <= N; ++i) scanf("%d %d %lld", &A[i], &H[i], &C[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 196092 KB Output is correct
2 Correct 87 ms 196156 KB Output is correct
3 Correct 87 ms 196112 KB Output is correct
4 Correct 89 ms 196060 KB Output is correct
5 Correct 1215 ms 196304 KB Output is correct
6 Correct 1193 ms 196328 KB Output is correct
7 Correct 1230 ms 196308 KB Output is correct
8 Correct 1135 ms 196304 KB Output is correct
9 Correct 1131 ms 196308 KB Output is correct
10 Correct 1154 ms 196308 KB Output is correct
11 Correct 1296 ms 196308 KB Output is correct
12 Correct 1058 ms 196932 KB Output is correct
13 Correct 1193 ms 196932 KB Output is correct
14 Correct 1065 ms 196656 KB Output is correct
15 Correct 1076 ms 196652 KB Output is correct
16 Correct 875 ms 196304 KB Output is correct
17 Correct 855 ms 196312 KB Output is correct
18 Correct 995 ms 196308 KB Output is correct
19 Correct 907 ms 196676 KB Output is correct
20 Correct 951 ms 196676 KB Output is correct
21 Correct 933 ms 196576 KB Output is correct
22 Correct 721 ms 196284 KB Output is correct
23 Correct 835 ms 196284 KB Output is correct
24 Correct 1090 ms 196600 KB Output is correct
25 Correct 955 ms 196608 KB Output is correct
26 Correct 1012 ms 196924 KB Output is correct
27 Correct 996 ms 196520 KB Output is correct
28 Correct 1069 ms 196648 KB Output is correct
29 Correct 1065 ms 196804 KB Output is correct
30 Correct 981 ms 196648 KB Output is correct
31 Correct 991 ms 196652 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 196092 KB Output is correct
2 Correct 87 ms 196156 KB Output is correct
3 Correct 87 ms 196112 KB Output is correct
4 Correct 89 ms 196060 KB Output is correct
5 Correct 1215 ms 196304 KB Output is correct
6 Correct 1193 ms 196328 KB Output is correct
7 Correct 1230 ms 196308 KB Output is correct
8 Correct 1135 ms 196304 KB Output is correct
9 Correct 1131 ms 196308 KB Output is correct
10 Correct 1154 ms 196308 KB Output is correct
11 Correct 1296 ms 196308 KB Output is correct
12 Correct 1058 ms 196932 KB Output is correct
13 Correct 1193 ms 196932 KB Output is correct
14 Correct 1065 ms 196656 KB Output is correct
15 Correct 1076 ms 196652 KB Output is correct
16 Correct 875 ms 196304 KB Output is correct
17 Correct 855 ms 196312 KB Output is correct
18 Correct 995 ms 196308 KB Output is correct
19 Correct 907 ms 196676 KB Output is correct
20 Correct 951 ms 196676 KB Output is correct
21 Correct 933 ms 196576 KB Output is correct
22 Correct 721 ms 196284 KB Output is correct
23 Correct 835 ms 196284 KB Output is correct
24 Correct 1090 ms 196600 KB Output is correct
25 Correct 955 ms 196608 KB Output is correct
26 Correct 1012 ms 196924 KB Output is correct
27 Correct 996 ms 196520 KB Output is correct
28 Correct 1069 ms 196648 KB Output is correct
29 Correct 1065 ms 196804 KB Output is correct
30 Correct 981 ms 196648 KB Output is correct
31 Correct 991 ms 196652 KB Output is correct
32 Incorrect 467 ms 196164 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 196092 KB Output is correct
2 Correct 87 ms 196156 KB Output is correct
3 Correct 87 ms 196112 KB Output is correct
4 Correct 89 ms 196060 KB Output is correct
5 Correct 1215 ms 196304 KB Output is correct
6 Correct 1193 ms 196328 KB Output is correct
7 Correct 1230 ms 196308 KB Output is correct
8 Correct 1135 ms 196304 KB Output is correct
9 Correct 1131 ms 196308 KB Output is correct
10 Correct 1154 ms 196308 KB Output is correct
11 Correct 1296 ms 196308 KB Output is correct
12 Correct 1058 ms 196932 KB Output is correct
13 Correct 1193 ms 196932 KB Output is correct
14 Correct 1065 ms 196656 KB Output is correct
15 Correct 1076 ms 196652 KB Output is correct
16 Correct 875 ms 196304 KB Output is correct
17 Correct 855 ms 196312 KB Output is correct
18 Correct 995 ms 196308 KB Output is correct
19 Correct 907 ms 196676 KB Output is correct
20 Correct 951 ms 196676 KB Output is correct
21 Correct 933 ms 196576 KB Output is correct
22 Correct 721 ms 196284 KB Output is correct
23 Correct 835 ms 196284 KB Output is correct
24 Correct 1090 ms 196600 KB Output is correct
25 Correct 955 ms 196608 KB Output is correct
26 Correct 1012 ms 196924 KB Output is correct
27 Correct 996 ms 196520 KB Output is correct
28 Correct 1069 ms 196648 KB Output is correct
29 Correct 1065 ms 196804 KB Output is correct
30 Correct 981 ms 196648 KB Output is correct
31 Correct 991 ms 196652 KB Output is correct
32 Incorrect 467 ms 196164 KB Output isn't correct
33 Halted 0 ms 0 KB -