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 <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using ll = long long int;
ll h;
int main()
{
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::priority_queue<ll> leftprioq;
std::priority_queue<ll,
std::vector<ll>,
std::greater<ll> > rightprioq;
ll n, x, ans = 0;
std::cin >> n >> h;
std::cin >> x;
leftprioq.push(x);
rightprioq.push(x);
for (int i = 1; i < n; ++i)
{
std::cin >> x;
ll leftnodepos = leftprioq.top() - h*i;
ll rightnodepos = rightprioq.top() + h*i;
if (x < leftnodepos)
{
leftprioq.pop();
leftprioq.push(x + h * i);
leftprioq.push(x + h * i);
ans += leftnodepos - x;
rightprioq.push(leftnodepos - h * i);
}
else if (x > rightnodepos)
{
rightprioq.pop();
rightprioq.push(x - h*i);
rightprioq.push(x - h*i);
ans += x - rightnodepos;
leftprioq.push(rightnodepos + h * i);
}
else
{
leftprioq.push(x + h *i);
rightprioq.push(x-h*i);
}
}
std::cout << ans;
}
# | 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... |