# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1046434 | 2024-08-06T14:33:01 Z | Zero_OP | Safety (NOI18_safety) | C++14 | 34 ms | 6312 KB |
#include<bits/stdc++.h> using namespace std; #define sz(v) (int)v.size() #define all(v) begin(v), end(v) #define compact(v) v.erase(unique(all(v)), end(v)) #define dbg(v) "[" #v " = " << (v) << "]" #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } template<typename T> bool minimize(T& a, const T& b){ if(a > b){ return a = b, true; } return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b){ return a = b, true; } return false; } template<int dimension, typename T> struct tensor : public vector<tensor<dimension - 1, T>> { static_assert(dimension > 0, "Dimension must be positive !\n"); template<typename... Args> tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {} }; template<typename T> struct tensor<1, T> : public vector<T> { tensor(int n = 0, T val = T()) : vector<T>(n, val) {} }; const int MAX = 2e5 + 5; int n, H, a[MAX]; void testcase(){ cin >> n >> H; for(int i = 0; i < n; ++i){ cin >> a[i]; } priority_queue<long long> lefts; priority_queue<long long, vector<long long>, greater<long long>> rights; long long ans = 0; lefts.push(a[0]); rights.push(a[0]); for(int i = 1; i < n; ++i){ long long shifted = 1LL * i * H; long long left_border = lefts.top() - shifted; long long right_border = rights.top() + shifted; if(a[i] < left_border){ lefts.push(a[i] + shifted); lefts.push(a[i] + shifted); lefts.pop(); rights.push(left_border - shifted); ans += abs(left_border - a[i]); } else if(a[i] > right_border){ rights.push(a[i] - shifted); rights.push(a[i] - shifted); rights.pop(); lefts.push(right_border + shifted); ans += abs(right_border - a[i]); } else{ lefts.push(a[i] + shifted); rights.push(a[i] - shifted); } } cout << ans << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); file("task"); int T = 1; // cin >> T; while(T--){ testcase(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 5332 KB | Output is correct |
2 | Correct | 29 ms | 6196 KB | Output is correct |
3 | Correct | 29 ms | 6184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 344 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 344 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 344 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 344 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 344 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 344 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 344 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 344 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 1 ms | 604 KB | Output is correct |
29 | Correct | 1 ms | 604 KB | Output is correct |
30 | Correct | 1 ms | 508 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 600 KB | Output is correct |
33 | Correct | 1 ms | 500 KB | Output is correct |
34 | Correct | 0 ms | 604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 344 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 468 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 344 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 344 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 344 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 0 ms | 348 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 348 KB | Output is correct |
33 | Correct | 0 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 604 KB | Output is correct |
35 | Correct | 1 ms | 604 KB | Output is correct |
36 | Correct | 1 ms | 508 KB | Output is correct |
37 | Correct | 0 ms | 348 KB | Output is correct |
38 | Correct | 0 ms | 600 KB | Output is correct |
39 | Correct | 1 ms | 500 KB | Output is correct |
40 | Correct | 0 ms | 604 KB | Output is correct |
41 | Correct | 1 ms | 604 KB | Output is correct |
42 | Correct | 1 ms | 604 KB | Output is correct |
43 | Correct | 1 ms | 604 KB | Output is correct |
44 | Correct | 1 ms | 604 KB | Output is correct |
45 | Correct | 1 ms | 604 KB | Output is correct |
46 | Correct | 1 ms | 520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 344 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 468 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 20 ms | 5332 KB | Output is correct |
20 | Correct | 29 ms | 6196 KB | Output is correct |
21 | Correct | 29 ms | 6184 KB | Output is correct |
22 | Correct | 1 ms | 344 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 344 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 344 KB | Output is correct |
30 | Correct | 0 ms | 348 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 348 KB | Output is correct |
33 | Correct | 0 ms | 348 KB | Output is correct |
34 | Correct | 0 ms | 348 KB | Output is correct |
35 | Correct | 0 ms | 348 KB | Output is correct |
36 | Correct | 0 ms | 348 KB | Output is correct |
37 | Correct | 1 ms | 604 KB | Output is correct |
38 | Correct | 1 ms | 604 KB | Output is correct |
39 | Correct | 1 ms | 508 KB | Output is correct |
40 | Correct | 0 ms | 348 KB | Output is correct |
41 | Correct | 0 ms | 600 KB | Output is correct |
42 | Correct | 1 ms | 500 KB | Output is correct |
43 | Correct | 0 ms | 604 KB | Output is correct |
44 | Correct | 1 ms | 604 KB | Output is correct |
45 | Correct | 1 ms | 604 KB | Output is correct |
46 | Correct | 1 ms | 604 KB | Output is correct |
47 | Correct | 1 ms | 604 KB | Output is correct |
48 | Correct | 1 ms | 604 KB | Output is correct |
49 | Correct | 1 ms | 520 KB | Output is correct |
50 | Correct | 34 ms | 6312 KB | Output is correct |
51 | Correct | 25 ms | 5828 KB | Output is correct |
52 | Correct | 17 ms | 5824 KB | Output is correct |
53 | Correct | 19 ms | 6212 KB | Output is correct |
54 | Correct | 28 ms | 6004 KB | Output is correct |
55 | Correct | 16 ms | 5832 KB | Output is correct |
56 | Correct | 19 ms | 6000 KB | Output is correct |
57 | Correct | 21 ms | 5820 KB | Output is correct |
58 | Correct | 21 ms | 5060 KB | Output is correct |
59 | Correct | 23 ms | 6084 KB | Output is correct |