Submission #796166

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-