답안 #796166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796166	2023-07-28T07:17:54 Z	이동현(#10071)	Security Guard (JOI23_guard)	C++17	25 / 100	41 ms	5020 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];

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]);
        }
    }

    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;
        if(!chk[now - 1] && !chk[now + 1]) ++gr;
        if(chk[now - 1] && chk[now + 1]) --gr;

        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	1 ms	1876 KB	Output is correct
2	Correct	22 ms	4940 KB	Output is correct
3	Correct	16 ms	5020 KB	Output is correct
4	Correct	18 ms	4996 KB	Output is correct
5	Correct	17 ms	4908 KB	Output is correct
6	Correct	17 ms	5004 KB	Output is correct
7	Correct	16 ms	4948 KB	Output is correct
8	Correct	1 ms	1876 KB	Output is correct

Subtask #2

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	22 ms	4940 KB	Output is correct
3	Correct	16 ms	5020 KB	Output is correct
4	Correct	18 ms	4996 KB	Output is correct
5	Correct	17 ms	4908 KB	Output is correct
6	Correct	17 ms	5004 KB	Output is correct
7	Correct	16 ms	4948 KB	Output is correct
8	Correct	1 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	40 ms	4996 KB	Output is correct
11	Correct	27 ms	5000 KB	Output is correct
12	Correct	24 ms	5004 KB	Output is correct
13	Correct	26 ms	4992 KB	Output is correct
14	Correct	41 ms	4988 KB	Output is correct
15	Correct	41 ms	4944 KB	Output is correct
16	Correct	40 ms	4948 KB	Output is correct
17	Correct	40 ms	4988 KB	Output is correct

Subtask #3

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	22 ms	4940 KB	Output is correct
3	Correct	16 ms	5020 KB	Output is correct
4	Correct	18 ms	4996 KB	Output is correct
5	Correct	17 ms	4908 KB	Output is correct
6	Correct	17 ms	5004 KB	Output is correct
7	Correct	16 ms	4948 KB	Output is correct
8	Correct	1 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	40 ms	4996 KB	Output is correct
11	Correct	27 ms	5000 KB	Output is correct
12	Correct	24 ms	5004 KB	Output is correct
13	Correct	26 ms	4992 KB	Output is correct
14	Correct	41 ms	4988 KB	Output is correct
15	Correct	41 ms	4944 KB	Output is correct
16	Correct	40 ms	4948 KB	Output is correct
17	Correct	40 ms	4988 KB	Output is correct
18	Incorrect	1 ms	1876 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	22 ms	4940 KB	Output is correct
3	Correct	16 ms	5020 KB	Output is correct
4	Correct	18 ms	4996 KB	Output is correct
5	Correct	17 ms	4908 KB	Output is correct
6	Correct	17 ms	5004 KB	Output is correct
7	Correct	16 ms	4948 KB	Output is correct
8	Correct	1 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	40 ms	4996 KB	Output is correct
11	Correct	27 ms	5000 KB	Output is correct
12	Correct	24 ms	5004 KB	Output is correct
13	Correct	26 ms	4992 KB	Output is correct
14	Correct	41 ms	4988 KB	Output is correct
15	Correct	41 ms	4944 KB	Output is correct
16	Correct	40 ms	4948 KB	Output is correct
17	Correct	40 ms	4988 KB	Output is correct
18	Incorrect	1 ms	1876 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 8.0

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

Subtask #6

0 / 18.0

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

Subtask #7

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	22 ms	4940 KB	Output is correct
3	Correct	16 ms	5020 KB	Output is correct
4	Correct	18 ms	4996 KB	Output is correct
5	Correct	17 ms	4908 KB	Output is correct
6	Correct	17 ms	5004 KB	Output is correct
7	Correct	16 ms	4948 KB	Output is correct
8	Correct	1 ms	1876 KB	Output is correct
9	Correct	1 ms	1876 KB	Output is correct
10	Correct	40 ms	4996 KB	Output is correct
11	Correct	27 ms	5000 KB	Output is correct
12	Correct	24 ms	5004 KB	Output is correct
13	Correct	26 ms	4992 KB	Output is correct
14	Correct	41 ms	4988 KB	Output is correct
15	Correct	41 ms	4944 KB	Output is correct
16	Correct	40 ms	4948 KB	Output is correct
17	Correct	40 ms	4988 KB	Output is correct
18	Incorrect	1 ms	1876 KB	Output isn't correct
19	Halted	0 ms	0 KB	-