Language: C++

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 1e8;
struct data {
  int l, r, value;
  data(int l, int r, int value) : l(l), r(r), value(value) {}
  data() {}
};
int a[maxn];
vector <data> dp[maxn];
int getValue(int i, int j) {
  for(auto k : dp[i]) {
    if(k.l <= j && j <= k.r) {
      return k.value;
    }
  }
  return inf;
}
int makeValue(int i, int j) {
  vector <int> interesting;
  interesting.push_back(0);
  interesting.push_back(j);
  interesting.push_back(a[i - 1] - a[i] + j);
  interesting.push_back(a[i - 1]);
  int ans = inf;
  for(int k : interesting) {
    int add = 0;
    if(k > j) ++add;
    if(a[i - 1] - k < a[i] - j) ++add;
    ans = min(ans, add + getValue(i - 1, k));
  }
  return ans;
}
// b_{i - 1} > b_{i}
// b_{i} < b_{i - 1}
// a_{i - 1} - b_{i - 1} < a_{i} - b_{i}
// a_{i - 1} - a_{i} + b_{i} < b_{i - 1} 

// [b_{i} + 1, a_{i - 1}] => +1
// [a_{i - 1} - a_{i} + b_{i} + 1, a_{i - 1}] => +1

int getRange(int i, int start) {
  int l = start, r = a[i];
  int value = makeValue(i, start);
  while(l < r) {
    int mid = (l + r + 1) >> 1;
    if(makeValue(i, mid) == value) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  dp[i].emplace_back(start, l, value);
  return l;
}

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  dp[0].emplace_back(0, 0, 0);
  a[0] = a[n + 1] = 0;
  for(int i = 1; i <= n + 1; i++) {
    int cur = 0;
    while(cur <= a[i]) {
      cur = getRange(i, cur) + 1;
    }
  }
  cout << getValue(n + 1, 0) << endl;
  return 0;
}


Compiler output:
a.cc:11:13: error: template argument 1 is invalid
   11 | vector <data> dp[maxn];
      |             ^
a.cc:11:13: error: template argument 2 is invalid
a.cc: In function 'int getValue(int, int)':
a.cc:13:20: error: 'begin' was not declared in this scope
   13 |   for(auto k : dp[i]) {
      |                    ^
a.cc:13:20: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:166,
                 from a.cc:1:
/usr/include/c++/14/valarray:1238:5: note:   'std::begin'
 1238 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
In file included from /usr/include/c++/14/filesystem:53,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:200:
/usr/include/c++/14/bits/fs_dir.h:608:3: note:   'std::filesystem::__cxx11::begin'
  608 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
a.cc:13:20: error: 'end' was not declared in this scope
   13 |   for(auto k : dp[i]) {
      |                    ^
a.cc:13:20: note: suggested alternatives:
/usr/include/c++/14/valarray:1265:5: note:   'std::end'
 1265 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/14/bits/fs_dir.h:613:3: note:   'std::filesystem::__cxx11::end'
  613 |   end(recursive_directory_iterator) noexcept
      |   ^~~
a.cc: In function 'int getRange(int, int)':
a.cc:54:9: error: request for member 'emplace_back' in 'dp[i]', which is of non-class type 'int'
   54 |   dp[i].emplace_back(start, l, value);
      |         ^~~~~~~~~~~~
a.cc: In function 'int main()':
a.cc:62:9: error: request for member 'emplace_back' in 'dp[0]', which is of non-class type 'int'
   62 |   dp[0].emplace_back(0, 0, 0);
      |         ^~~~~~~~~~~~