This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200'200;
int n;
ll h;
ll s[N];
void solve() {
cin >> n >> h;
for (int i = 1; i <= n; i++)
cin >> s[i];
set<ll> t1, t2;
t1.insert(s[1]);
t2.insert(s[1]);
ll base = 0;
for (int i = 2; i <= n; i++) {
set<ll> st;
{
for (ll c : t1) st.insert(c - h);
t1 = st;
st.clear();
}
{
for (ll c : t2) st.insert(c + h);
t2 = st;
st.clear();
}
ll l = *(--t1.end()), r = *t2.begin();
if (l <= s[i] && s[i] <= r) {
t1.insert(s[i]);
t2.insert(s[i]);
} else if (s[i] < l) {
t1.insert(s[i]);
t1.insert(s[i]);
t1.erase(l);
t2.insert(l);
base += l - s[i];
} else {
t2.insert(s[i]);
t2.insert(s[i]);
t2.erase(r);
t1.insert(r);
base += s[i] - r;
}
}
cout << base;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int test_cases = 1;
// cin >> test_cases;
while (test_cases-->0) {
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |