Language: C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll is_query = -(1LL<<62);
struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return (long double)(x->b - y->b)*(z->m - y->m) >= (long double)(y->b - z->b)*(y->m - x->m);
    }
    void insert_line(ll m, ll b) {
        auto y = insert({ m, b });
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        while (y != begin() && bad(prev(y))) erase(prev(y));
    }
    ll eval(ll x) {
        auto l = *lower_bound((Line) { x, is_query });
        return l.m * x + l.b;
    }
};
int main(){
  int n; long long c; cin >> n >> c;
  vector<long long> h(n); for(auto & i : h) cin >> i;
  vector<long long> f(n);
  HullDynamic magic;
  magic.insert(- 2 * h[n - 1], h[n - 1] * h[n - 1] + c);
  for(int i = n - 2; i >= 0; i--){
    long long best = magic.eval(h[i]);
    f[i] = best + h[i] * h[i];
    magic.insert(- 2 * h[i], h[i] * h[i] + c + f[i]);
  }
  cout << f[0] << endl;
  return 0;
}


Compiler output:
In file included from /usr/include/c++/14/set:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:158,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_multiset.h: In instantiation of 'void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = long long int; _Key = Line; _Compare = std::less<Line>; _Alloc = std::allocator<Line>]':
a.cc:44:15:   required from here
   44 |   magic.insert(- 2 * h[n - 1], h[n - 1] * h[n - 1] + c);
      |   ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_multiset.h:554:37: error: no matching function for call to 'std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<Line>, std::allocator<Line> >::_M_insert_range_equal(long long int&, long long int&)'
  554 |         { _M_t._M_insert_range_equal(__first, __last); }
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:152:
/usr/include/c++/14/bits/stl_tree.h:1113:9: note: candidate: 'template<class _InputIterator> std::__enable_if_t<((bool)std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value)> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_equal(_InputIterator, _InputIterator) [with _Key = Line; _Val = Line; _KeyOfValue = std::_Identity<Line>; _Compare = std::less<Line>; _Alloc = std::allocator<Line>]'
 1113 |         _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1113:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<((bool)std::is_same<Line, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value), void> std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<Line>, std::allocator<Line> >::_M_insert_range_equal(_InputIterator, _InputIterator) [with _InputIterator = long long int]':
/usr/include/c++/14/bits/stl_multiset.h:554:30:   required from 'void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = long long int; _Key = Line; _Compare = std::less<Line>; _Alloc = std::allocator<Line>]'
  554 |         { _M_t._M_insert_range_equal(__first, __last); }
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
a.cc:44:15:   required from here
   44 |   magic.insert(- 2 * h[n - 1], h[n - 1] * h[n - 1] + c);
      |   ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1095:58: error: no type named 'value_type' in 'struct std::iterator_traits<long long int>'
 1095 |         __enable_if_t<__same_value_type<_InputIterator>::value>
      |                                                          ^~~~~
/usr/include/c++/14/bits/stl_multiset.h: In instantiation of 'void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = long long int; _Key = Line; _Compare = std::less<Line>; _Alloc = std::allocator<Line>]':
a.cc:44:15:   required from here
   44 |   magic.insert(- 2 * h[n - 1], h[n - 1] * h[n - 1] + c);
      |   ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1122:9: note: candidate: 'template<class _InputIterator> std::__enable_if_t<((bool)(! std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value))> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_equal(_InputIterator, _InputIterator) [with _Key = Line; _Val = Line; _KeyOfValue = std::_Identity<Line>; _Compare = std::less<Line>; _Alloc = std::allocator<Line>]'
 1122 |         _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1122:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<((bool)(! std::is_same<Line, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value)), void> std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<Line>, std::allocator<Line> >::_M_insert_range_equal(_InputIterator, _InputIterator) [with _InputIterator = long long int]':
/usr/include/c++/14/bits/stl_multiset.h:554:30:   required from 'void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = long long int; _Key = Line; _Compare = std::less<Line>; _Alloc = std::allocator<Line>]'
  554 |         { _M_t._M_insert_range_equal(__first, __last); }
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
a.cc:44:15:   required from here
   44 |   magic.insert(- 2 * h[n - 1], h[n - 1] * h[n - 1] + c);
      |   ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1104:59: error: no type named 'value_type' in 'struct std::iterator_traits<long long int>'
 1104 |         __enable_if_t<!__same_value_type<_InputIterator>::value>
      |                                                           ^~~~~