#include <bits/stdc++.h> using namespace std; typedef long long ll; struct point { ll x, y; }; const int MAXN = 2e5+5; vector<point> s; int v[MAXN]; int n, x; void expand() { ll mn = 1e18; for(auto pp : s) mn = min(mn, pp.y); int l = -1, r = -1; for(int i = 0; i < s.size(); i++) { if(s[i].y == mn) { if(l == -1) l = i; r = i; } } vector<point> aux; for(int i = 0; i < s.size(); i++) { if(i <= l) aux.push_back({s[i].x-x, s[i].y}); if(i >= r) aux.push_back({s[i].x+x, s[i].y}); } swap(aux, s); } void update(ll cur) { if(s.empty()) { s.push_back({v[cur], 0}); return; } expand(); // printf("bleh %lld\n", cur); // for(auto pp : s) printf("(%lld %lld) ", pp.x, pp.y); cout << endl; vector<point> aux; for(int i = 0; i < s.size(); i++) { if(s[i].x >= v[cur]) { if(i == 0) aux.push_back({ v[cur], s[i].y+(s[i].x-v[cur])*(cur-1) }); else aux.push_back({ v[cur], ((v[cur]-s[i-1].x)*(s[i].y-s[i-1].y))/(s[i].x-s[i-1].x)+s[i-1].y }); break; } aux.push_back(s[i]); } for(auto pp : s) if(pp.x >= v[cur]) aux.push_back(pp); if(aux.size() == s.size()) aux.push_back({ v[cur], (v[cur]-s.back().x)*(cur-1)+s.back().y }); for(int i = 0; i < aux.size(); i++) aux[i].y += abs(aux[i].x-v[cur]); swap(aux, s); // for(auto pp : s) printf("(%lld %lld) ", pp.x, pp.y); cout << endl; } int main() { scanf("%d %d", &n, &x); for(int i = 1; i <= n; i++) { scanf("%d", &v[i]); update(i); } ll ans = 1e18; for(auto cur : s) ans = min(ans, cur.y); printf("%lld\n", ans); }

safety.cpp: In function 'void expand()':
safety.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
safety.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
safety.cpp: In function 'void update(ll)':
safety.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
safety.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < aux.size(); i++) aux[i].y += abs(aux[i].x-v[cur]);
                 ~~^~~~~~~~~~~~
safety.cpp: In function 'int main()':
safety.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &x);
  ~~~~~^~~~~~~~~~~~~~~~~
safety.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~