답안 #796171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796171	2023-07-28T07:20:20 Z	이동현(#10071)	Security Guard (JOI23_guard)	C++17	25 / 100	107 ms	16288 KB

guard

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)2e5 + 4;
int n, m, q;
int a[NS], srt[NS], chk[NS];
vector<int> way[NS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        if(i > 1){
            ans += min(a[i - 1], a[i]);
        }
    }
    for(int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >> y;
        way[x].push_back(y);
        way[y].push_back(x);
    }

    iota(srt, srt + NS, 0);
    sort(srt + 1, srt + n + 1, [&](int x, int y){return a[x] > a[y];});

    int gr = 1;
    chk[0] = chk[n + 1] = 1;
    for(int i = 1; i <= n; ++i){
        int now = srt[i];
        
        chk[now] = 1;
        gr += (int)way[now].size() - 1;
        for(auto&nxt:way[now]){
            gr -= chk[nxt];
        }

        ans += gr * (a[srt[i]] - a[srt[i + 1]]);
    }

    assert(gr == 0);

    cout << ans << '\n';
    
    return 0;
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	59 ms	16128 KB	Output is correct
3	Correct	64 ms	16104 KB	Output is correct
4	Correct	65 ms	16076 KB	Output is correct
5	Correct	69 ms	16120 KB	Output is correct
6	Correct	67 ms	16096 KB	Output is correct
7	Correct	65 ms	16152 KB	Output is correct
8	Correct	4 ms	6484 KB	Output is correct

Subtask #2

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	59 ms	16128 KB	Output is correct
3	Correct	64 ms	16104 KB	Output is correct
4	Correct	65 ms	16076 KB	Output is correct
5	Correct	69 ms	16120 KB	Output is correct
6	Correct	67 ms	16096 KB	Output is correct
7	Correct	65 ms	16152 KB	Output is correct
8	Correct	4 ms	6484 KB	Output is correct
9	Correct	3 ms	6484 KB	Output is correct
10	Correct	92 ms	16204 KB	Output is correct
11	Correct	70 ms	16232 KB	Output is correct
12	Correct	67 ms	16232 KB	Output is correct
13	Correct	70 ms	16288 KB	Output is correct
14	Correct	94 ms	16196 KB	Output is correct
15	Correct	94 ms	16176 KB	Output is correct
16	Correct	93 ms	16176 KB	Output is correct
17	Correct	107 ms	16252 KB	Output is correct

Subtask #3

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	59 ms	16128 KB	Output is correct
3	Correct	64 ms	16104 KB	Output is correct
4	Correct	65 ms	16076 KB	Output is correct
5	Correct	69 ms	16120 KB	Output is correct
6	Correct	67 ms	16096 KB	Output is correct
7	Correct	65 ms	16152 KB	Output is correct
8	Correct	4 ms	6484 KB	Output is correct
9	Correct	3 ms	6484 KB	Output is correct
10	Correct	92 ms	16204 KB	Output is correct
11	Correct	70 ms	16232 KB	Output is correct
12	Correct	67 ms	16232 KB	Output is correct
13	Correct	70 ms	16288 KB	Output is correct
14	Correct	94 ms	16196 KB	Output is correct
15	Correct	94 ms	16176 KB	Output is correct
16	Correct	93 ms	16176 KB	Output is correct
17	Correct	107 ms	16252 KB	Output is correct
18	Incorrect	4 ms	6484 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	59 ms	16128 KB	Output is correct
3	Correct	64 ms	16104 KB	Output is correct
4	Correct	65 ms	16076 KB	Output is correct
5	Correct	69 ms	16120 KB	Output is correct
6	Correct	67 ms	16096 KB	Output is correct
7	Correct	65 ms	16152 KB	Output is correct
8	Correct	4 ms	6484 KB	Output is correct
9	Correct	3 ms	6484 KB	Output is correct
10	Correct	92 ms	16204 KB	Output is correct
11	Correct	70 ms	16232 KB	Output is correct
12	Correct	67 ms	16232 KB	Output is correct
13	Correct	70 ms	16288 KB	Output is correct
14	Correct	94 ms	16196 KB	Output is correct
15	Correct	94 ms	16176 KB	Output is correct
16	Correct	93 ms	16176 KB	Output is correct
17	Correct	107 ms	16252 KB	Output is correct
18	Incorrect	4 ms	6484 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 8.0

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

Subtask #6

0 / 18.0

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

Subtask #7

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	59 ms	16128 KB	Output is correct
3	Correct	64 ms	16104 KB	Output is correct
4	Correct	65 ms	16076 KB	Output is correct
5	Correct	69 ms	16120 KB	Output is correct
6	Correct	67 ms	16096 KB	Output is correct
7	Correct	65 ms	16152 KB	Output is correct
8	Correct	4 ms	6484 KB	Output is correct
9	Correct	3 ms	6484 KB	Output is correct
10	Correct	92 ms	16204 KB	Output is correct
11	Correct	70 ms	16232 KB	Output is correct
12	Correct	67 ms	16232 KB	Output is correct
13	Correct	70 ms	16288 KB	Output is correct
14	Correct	94 ms	16196 KB	Output is correct
15	Correct	94 ms	16176 KB	Output is correct
16	Correct	93 ms	16176 KB	Output is correct
17	Correct	107 ms	16252 KB	Output is correct
18	Incorrect	4 ms	6484 KB	Output isn't correct
19	Halted	0 ms	0 KB	-