Submission #1030880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1030880	2024-07-22T11:14:56 Z	Unforgettablepl	Security Guard (JOI23_guard)	C++17	37 / 100	775 ms	1048576 KB

guard

#include <bits/stdc++.h>
using namespace std;

#define int long long



int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;
	cin >> n >> m >> q;
	vector<int> arr(n+1);
	for(int i=1;i<=n;i++)cin>>arr[i];
	vector<vector<int>> adj(n+1);
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	int ans = 0;
	int currmax = 0;
	function<void(int,int,int,int)> dfs = [&](int x,int p,int curr,int curroffset){
		ans+=arr[p];
		curr+=arr[p];
		curr-=arr[x];
		if(curr<0){
			curroffset-=curr;
			currmax=max(currmax,curroffset);
			curr = 0;
		}
		for(int&i:adj[x])if(i!=p)dfs(i,x,curr,curroffset);
	};
	dfs(1,0,arr[1],0);
	cout << ans+currmax << '\n';
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	60 ms	40780 KB	Output is correct
3	Correct	59 ms	40784 KB	Output is correct
4	Correct	56 ms	40908 KB	Output is correct
5	Correct	60 ms	40788 KB	Output is correct
6	Correct	62 ms	40888 KB	Output is correct
7	Correct	58 ms	40784 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	60 ms	40780 KB	Output is correct
3	Correct	59 ms	40784 KB	Output is correct
4	Correct	56 ms	40908 KB	Output is correct
5	Correct	60 ms	40788 KB	Output is correct
6	Correct	62 ms	40888 KB	Output is correct
7	Correct	58 ms	40784 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	65 ms	42376 KB	Output is correct
11	Correct	70 ms	42456 KB	Output is correct
12	Correct	65 ms	42320 KB	Output is correct
13	Correct	64 ms	42440 KB	Output is correct
14	Correct	64 ms	42320 KB	Output is correct
15	Correct	67 ms	42324 KB	Output is correct
16	Correct	67 ms	42376 KB	Output is correct
17	Correct	66 ms	42320 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	60 ms	40780 KB	Output is correct
3	Correct	59 ms	40784 KB	Output is correct
4	Correct	56 ms	40908 KB	Output is correct
5	Correct	60 ms	40788 KB	Output is correct
6	Correct	62 ms	40888 KB	Output is correct
7	Correct	58 ms	40784 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	65 ms	42376 KB	Output is correct
11	Correct	70 ms	42456 KB	Output is correct
12	Correct	65 ms	42320 KB	Output is correct
13	Correct	64 ms	42440 KB	Output is correct
14	Correct	64 ms	42320 KB	Output is correct
15	Correct	67 ms	42324 KB	Output is correct
16	Correct	67 ms	42376 KB	Output is correct
17	Correct	66 ms	42320 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	112 ms	33868 KB	Output is correct
20	Correct	84 ms	28184 KB	Output is correct
21	Correct	76 ms	18516 KB	Output is correct
22	Correct	66 ms	18516 KB	Output is correct
23	Correct	61 ms	19284 KB	Output is correct
24	Correct	60 ms	19280 KB	Output is correct
25	Correct	58 ms	18872 KB	Output is correct
26	Correct	54 ms	18744 KB	Output is correct
27	Correct	51 ms	18884 KB	Output is correct
28	Correct	80 ms	35404 KB	Output is correct
29	Correct	71 ms	29640 KB	Output is correct
30	Correct	59 ms	22332 KB	Output is correct
31	Correct	50 ms	18884 KB	Output is correct
32	Correct	64 ms	18892 KB	Output is correct
33	Correct	67 ms	18772 KB	Output is correct
34	Correct	68 ms	18528 KB	Output is correct
35	Correct	71 ms	19540 KB	Output is correct
36	Correct	70 ms	19648 KB	Output is correct
37	Correct	64 ms	19540 KB	Output is correct
38	Correct	72 ms	27852 KB	Output is correct
39	Correct	68 ms	30276 KB	Output is correct
40	Correct	69 ms	23368 KB	Output is correct
41	Correct	75 ms	40276 KB	Output is correct
42	Correct	98 ms	41044 KB	Output is correct
43	Correct	70 ms	18516 KB	Output is correct
44	Correct	71 ms	18516 KB	Output is correct
45	Correct	68 ms	18528 KB	Output is correct
46	Correct	69 ms	18516 KB	Output is correct
47	Correct	86 ms	18516 KB	Output is correct
48	Correct	68 ms	18436 KB	Output is correct
49	Correct	80 ms	18772 KB	Output is correct
50	Correct	64 ms	18436 KB	Output is correct
51	Correct	70 ms	18788 KB	Output is correct
52	Correct	57 ms	16980 KB	Output is correct

Subtask #4
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	60 ms	40780 KB	Output is correct
3	Correct	59 ms	40784 KB	Output is correct
4	Correct	56 ms	40908 KB	Output is correct
5	Correct	60 ms	40788 KB	Output is correct
6	Correct	62 ms	40888 KB	Output is correct
7	Correct	58 ms	40784 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	65 ms	42376 KB	Output is correct
11	Correct	70 ms	42456 KB	Output is correct
12	Correct	65 ms	42320 KB	Output is correct
13	Correct	64 ms	42440 KB	Output is correct
14	Correct	64 ms	42320 KB	Output is correct
15	Correct	67 ms	42324 KB	Output is correct
16	Correct	67 ms	42376 KB	Output is correct
17	Correct	66 ms	42320 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	112 ms	33868 KB	Output is correct
20	Correct	84 ms	28184 KB	Output is correct
21	Correct	76 ms	18516 KB	Output is correct
22	Correct	66 ms	18516 KB	Output is correct
23	Correct	61 ms	19284 KB	Output is correct
24	Correct	60 ms	19280 KB	Output is correct
25	Correct	58 ms	18872 KB	Output is correct
26	Correct	54 ms	18744 KB	Output is correct
27	Correct	51 ms	18884 KB	Output is correct
28	Correct	80 ms	35404 KB	Output is correct
29	Correct	71 ms	29640 KB	Output is correct
30	Correct	59 ms	22332 KB	Output is correct
31	Correct	50 ms	18884 KB	Output is correct
32	Correct	64 ms	18892 KB	Output is correct
33	Correct	67 ms	18772 KB	Output is correct
34	Correct	68 ms	18528 KB	Output is correct
35	Correct	71 ms	19540 KB	Output is correct
36	Correct	70 ms	19648 KB	Output is correct
37	Correct	64 ms	19540 KB	Output is correct
38	Correct	72 ms	27852 KB	Output is correct
39	Correct	68 ms	30276 KB	Output is correct
40	Correct	69 ms	23368 KB	Output is correct
41	Correct	75 ms	40276 KB	Output is correct
42	Correct	98 ms	41044 KB	Output is correct
43	Correct	70 ms	18516 KB	Output is correct
44	Correct	71 ms	18516 KB	Output is correct
45	Correct	68 ms	18528 KB	Output is correct
46	Correct	69 ms	18516 KB	Output is correct
47	Correct	86 ms	18516 KB	Output is correct
48	Correct	68 ms	18436 KB	Output is correct
49	Correct	80 ms	18772 KB	Output is correct
50	Correct	64 ms	18436 KB	Output is correct
51	Correct	70 ms	18788 KB	Output is correct
52	Correct	57 ms	16980 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Runtime error	775 ms	1048576 KB	Execution killed with signal 9
55	Halted	0 ms	0 KB	-

Subtask #5
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	60 ms	40780 KB	Output is correct
3	Correct	59 ms	40784 KB	Output is correct
4	Correct	56 ms	40908 KB	Output is correct
5	Correct	60 ms	40788 KB	Output is correct
6	Correct	62 ms	40888 KB	Output is correct
7	Correct	58 ms	40784 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	65 ms	42376 KB	Output is correct
11	Correct	70 ms	42456 KB	Output is correct
12	Correct	65 ms	42320 KB	Output is correct
13	Correct	64 ms	42440 KB	Output is correct
14	Correct	64 ms	42320 KB	Output is correct
15	Correct	67 ms	42324 KB	Output is correct
16	Correct	67 ms	42376 KB	Output is correct
17	Correct	66 ms	42320 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	112 ms	33868 KB	Output is correct
20	Correct	84 ms	28184 KB	Output is correct
21	Correct	76 ms	18516 KB	Output is correct
22	Correct	66 ms	18516 KB	Output is correct
23	Correct	61 ms	19284 KB	Output is correct
24	Correct	60 ms	19280 KB	Output is correct
25	Correct	58 ms	18872 KB	Output is correct
26	Correct	54 ms	18744 KB	Output is correct
27	Correct	51 ms	18884 KB	Output is correct
28	Correct	80 ms	35404 KB	Output is correct
29	Correct	71 ms	29640 KB	Output is correct
30	Correct	59 ms	22332 KB	Output is correct
31	Correct	50 ms	18884 KB	Output is correct
32	Correct	64 ms	18892 KB	Output is correct
33	Correct	67 ms	18772 KB	Output is correct
34	Correct	68 ms	18528 KB	Output is correct
35	Correct	71 ms	19540 KB	Output is correct
36	Correct	70 ms	19648 KB	Output is correct
37	Correct	64 ms	19540 KB	Output is correct
38	Correct	72 ms	27852 KB	Output is correct
39	Correct	68 ms	30276 KB	Output is correct
40	Correct	69 ms	23368 KB	Output is correct
41	Correct	75 ms	40276 KB	Output is correct
42	Correct	98 ms	41044 KB	Output is correct
43	Correct	70 ms	18516 KB	Output is correct
44	Correct	71 ms	18516 KB	Output is correct
45	Correct	68 ms	18528 KB	Output is correct
46	Correct	69 ms	18516 KB	Output is correct
47	Correct	86 ms	18516 KB	Output is correct
48	Correct	68 ms	18436 KB	Output is correct
49	Correct	80 ms	18772 KB	Output is correct
50	Correct	64 ms	18436 KB	Output is correct
51	Correct	70 ms	18788 KB	Output is correct
52	Correct	57 ms	16980 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Runtime error	775 ms	1048576 KB	Execution killed with signal 9
55	Halted	0 ms	0 KB	-

Submission #1030880

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 13.0 / 13.0

Subtask #3 12.0 / 12.0

Subtask #4 0 / 13.0

Subtask #5 0 / 8.0

Subtask #6 0 / 18.0

Subtask #7 0 / 24.0

Subtask #1
12.0 / 12.0

Subtask #2
13.0 / 13.0

Subtask #3
12.0 / 12.0

Subtask #4
0 / 13.0

Subtask #5
0 / 8.0

Subtask #6
0 / 18.0

Subtask #7
0 / 24.0