답안 #968382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
968382	2024-04-23T11:13:19 Z	josanneo22	Security Guard (JOI23_guard)	C++17	25 / 100	69 ms	19024 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 && *max_element(S + 1, S + 1 + N) <= 2 && is_chain()) {
		i64 ans = solve1();
		reverse(S + 1, S + 1 + N);
		ans = max(ans, solve1());
		cout << ans << '\n';
	}
	else if (M == N - 1 && Q == 0 && is_chain()) {
		i64 ans = solve2();
		cout << ans << '\n';
	}
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	52 ms	17236 KB	Output is correct
3	Correct	48 ms	17232 KB	Output is correct
4	Correct	49 ms	17236 KB	Output is correct
5	Correct	49 ms	17232 KB	Output is correct
6	Correct	51 ms	17300 KB	Output is correct
7	Correct	48 ms	17248 KB	Output is correct
8	Correct	2 ms	7004 KB	Output is correct

Subtask #2

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	52 ms	17236 KB	Output is correct
3	Correct	48 ms	17232 KB	Output is correct
4	Correct	49 ms	17236 KB	Output is correct
5	Correct	49 ms	17232 KB	Output is correct
6	Correct	51 ms	17300 KB	Output is correct
7	Correct	48 ms	17248 KB	Output is correct
8	Correct	2 ms	7004 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	18800 KB	Output is correct
11	Correct	56 ms	19024 KB	Output is correct
12	Correct	66 ms	18936 KB	Output is correct
13	Correct	55 ms	18904 KB	Output is correct
14	Correct	57 ms	18768 KB	Output is correct
15	Correct	55 ms	18772 KB	Output is correct
16	Correct	69 ms	18772 KB	Output is correct
17	Correct	59 ms	18940 KB	Output is correct

Subtask #3

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	52 ms	17236 KB	Output is correct
3	Correct	48 ms	17232 KB	Output is correct
4	Correct	49 ms	17236 KB	Output is correct
5	Correct	49 ms	17232 KB	Output is correct
6	Correct	51 ms	17300 KB	Output is correct
7	Correct	48 ms	17248 KB	Output is correct
8	Correct	2 ms	7004 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	18800 KB	Output is correct
11	Correct	56 ms	19024 KB	Output is correct
12	Correct	66 ms	18936 KB	Output is correct
13	Correct	55 ms	18904 KB	Output is correct
14	Correct	57 ms	18768 KB	Output is correct
15	Correct	55 ms	18772 KB	Output is correct
16	Correct	69 ms	18772 KB	Output is correct
17	Correct	59 ms	18940 KB	Output is correct
18	Incorrect	2 ms	6748 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	52 ms	17236 KB	Output is correct
3	Correct	48 ms	17232 KB	Output is correct
4	Correct	49 ms	17236 KB	Output is correct
5	Correct	49 ms	17232 KB	Output is correct
6	Correct	51 ms	17300 KB	Output is correct
7	Correct	48 ms	17248 KB	Output is correct
8	Correct	2 ms	7004 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	18800 KB	Output is correct
11	Correct	56 ms	19024 KB	Output is correct
12	Correct	66 ms	18936 KB	Output is correct
13	Correct	55 ms	18904 KB	Output is correct
14	Correct	57 ms	18768 KB	Output is correct
15	Correct	55 ms	18772 KB	Output is correct
16	Correct	69 ms	18772 KB	Output is correct
17	Correct	59 ms	18940 KB	Output is correct
18	Incorrect	2 ms	6748 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6796 KB	Output is correct
2	Incorrect	1 ms	6748 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6796 KB	Output is correct
2	Incorrect	1 ms	6748 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	52 ms	17236 KB	Output is correct
3	Correct	48 ms	17232 KB	Output is correct
4	Correct	49 ms	17236 KB	Output is correct
5	Correct	49 ms	17232 KB	Output is correct
6	Correct	51 ms	17300 KB	Output is correct
7	Correct	48 ms	17248 KB	Output is correct
8	Correct	2 ms	7004 KB	Output is correct
9	Correct	1 ms	6748 KB	Output is correct
10	Correct	57 ms	18800 KB	Output is correct
11	Correct	56 ms	19024 KB	Output is correct
12	Correct	66 ms	18936 KB	Output is correct
13	Correct	55 ms	18904 KB	Output is correct
14	Correct	57 ms	18768 KB	Output is correct
15	Correct	55 ms	18772 KB	Output is correct
16	Correct	69 ms	18772 KB	Output is correct
17	Correct	59 ms	18940 KB	Output is correct
18	Incorrect	2 ms	6748 KB	Output isn't correct
19	Halted	0 ms	0 KB	-