Submission #968383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
968383	2024-04-23T11:13:40 Z	josanneo22	Security Guard (JOI23_guard)	C++17	25 / 100	57 ms	14520 KB

guard

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

const int nax = 200005;
int N, M, Q;
int _u[nax], _v[nax];
i64 S[nax]; 
vector<int> G[nax];
bool is_chain() {
	for (int i = 0; i < M; i++) 
		if (_u[i] != i + 1 || _v[i] != i + 2) 
			return false;
	return true;
}
i64 solve1() {
	i64 ans = 0;
	for (int i = 2; i <= N; i++) ans += max(S[i], S[i - 1]);
	for (int i = 1; i <= N - 2; i++) ans -= max(0LL, S[i] - S[i + 1]);
	// last one cannot save anything
	return ans;
}
i64 solve2() {
	i64 ans = 0;
	// 1 -> 2 -> 3 -> ... -> N - 1 -> N
	// get a[2], a[3], a[4]... a[N - 1]
	for (int i = 2; i <= N - 1; i++) ans += S[i];
	return ans + *max_element(S + 1, S + 1 + N);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M >> Q;
	for (int i = 1; i <= N; i++) cin >> S[i];
	for (int i = 0; i < M; i++) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		_u[i] = u; _v[i] = v;
	}
	if (M == N - 1 && Q == 0 && is_chain()) {
		i64 ans = solve2();
		cout << ans << '\n';
	}
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6748 KB	Output is correct
2	Correct	47 ms	14520 KB	Output is correct
3	Correct	45 ms	14420 KB	Output is correct
4	Correct	45 ms	14428 KB	Output is correct
5	Correct	46 ms	14420 KB	Output is correct
6	Correct	46 ms	14420 KB	Output is correct
7	Correct	51 ms	14420 KB	Output is correct
8	Correct	2 ms	6748 KB	Output is correct

Subtask #2

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6748 KB	Output is correct
2	Correct	47 ms	14520 KB	Output is correct
3	Correct	45 ms	14420 KB	Output is correct
4	Correct	45 ms	14428 KB	Output is correct
5	Correct	46 ms	14420 KB	Output is correct
6	Correct	46 ms	14420 KB	Output is correct
7	Correct	51 ms	14420 KB	Output is correct
8	Correct	2 ms	6748 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	14360 KB	Output is correct
11	Correct	57 ms	14416 KB	Output is correct
12	Correct	52 ms	14420 KB	Output is correct
13	Correct	51 ms	14508 KB	Output is correct
14	Correct	53 ms	14416 KB	Output is correct
15	Correct	52 ms	14388 KB	Output is correct
16	Correct	53 ms	14420 KB	Output is correct
17	Correct	53 ms	14308 KB	Output is correct

Subtask #3

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6748 KB	Output is correct
2	Correct	47 ms	14520 KB	Output is correct
3	Correct	45 ms	14420 KB	Output is correct
4	Correct	45 ms	14428 KB	Output is correct
5	Correct	46 ms	14420 KB	Output is correct
6	Correct	46 ms	14420 KB	Output is correct
7	Correct	51 ms	14420 KB	Output is correct
8	Correct	2 ms	6748 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	14360 KB	Output is correct
11	Correct	57 ms	14416 KB	Output is correct
12	Correct	52 ms	14420 KB	Output is correct
13	Correct	51 ms	14508 KB	Output is correct
14	Correct	53 ms	14416 KB	Output is correct
15	Correct	52 ms	14388 KB	Output is correct
16	Correct	53 ms	14420 KB	Output is correct
17	Correct	53 ms	14308 KB	Output is correct
18	Incorrect	1 ms	6748 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6748 KB	Output is correct
2	Correct	47 ms	14520 KB	Output is correct
3	Correct	45 ms	14420 KB	Output is correct
4	Correct	45 ms	14428 KB	Output is correct
5	Correct	46 ms	14420 KB	Output is correct
6	Correct	46 ms	14420 KB	Output is correct
7	Correct	51 ms	14420 KB	Output is correct
8	Correct	2 ms	6748 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	14360 KB	Output is correct
11	Correct	57 ms	14416 KB	Output is correct
12	Correct	52 ms	14420 KB	Output is correct
13	Correct	51 ms	14508 KB	Output is correct
14	Correct	53 ms	14416 KB	Output is correct
15	Correct	52 ms	14388 KB	Output is correct
16	Correct	53 ms	14420 KB	Output is correct
17	Correct	53 ms	14308 KB	Output is correct
18	Incorrect	1 ms	6748 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6752 KB	Output is correct
2	Incorrect	1 ms	6752 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	6752 KB	Output is correct
2	Incorrect	1 ms	6752 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6748 KB	Output is correct
2	Correct	47 ms	14520 KB	Output is correct
3	Correct	45 ms	14420 KB	Output is correct
4	Correct	45 ms	14428 KB	Output is correct
5	Correct	46 ms	14420 KB	Output is correct
6	Correct	46 ms	14420 KB	Output is correct
7	Correct	51 ms	14420 KB	Output is correct
8	Correct	2 ms	6748 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	14360 KB	Output is correct
11	Correct	57 ms	14416 KB	Output is correct
12	Correct	52 ms	14420 KB	Output is correct
13	Correct	51 ms	14508 KB	Output is correct
14	Correct	53 ms	14416 KB	Output is correct
15	Correct	52 ms	14388 KB	Output is correct
16	Correct	53 ms	14420 KB	Output is correct
17	Correct	53 ms	14308 KB	Output is correct
18	Incorrect	1 ms	6748 KB	Output isn't correct
19	Halted	0 ms	0 KB	-