#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
inline int pow2(int i) { return 1 << i; }
const int lg = 16;
int lg[100'001];
struct Sparse
{
int t[lg + 1][100'000];
void set(int i, int val)
{
t[0][i] = val;
for (int j = 1; j <= lg && pow2(j) <= i + 1; ++j)
t[j][i] = min(t[j - 1][i], t[j - 1][i - pow2(j - 1)]);
}
int operator()(int l, int r)
{
int i = lg[r - l + 1];
return min(t[i][r], t[i][l + pow2(i) - 1]);
}
};
Sparse dp[101];
int main()
{
for (int i = 1; i <= 100'000; ++i)
lg[i] = __lg(i);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
dp[1].set(0, a[0]);
for (int i = 1; i < n; ++i)
dp[1].set(i, max(dp[1](i - 1, i - 1), a[i]));
for (int j = 2; j <= k; ++j)
dp[j].set(0, 1000'000 * k + 1);
vector<int> st;
for (int i = 1; i < n; ++i)
{
auto it = upper_bound(st.rbegin(), st.rend(), i, [&a](int i, int j){ return a[i] < a[j]; });
int m = (it == st.rend() ? -1 : *it);
for (int j = 2; j <= k; ++j)
{
int cur = 1000'000 * k + 1;
if (m != -1)
cur = min(cur, dp[j](m, m));
else
m = 0;
if (m < i)
cur = min(cur, dp[j - 1](m, i - 1) + a[i]);
dp[j].set(i, cur);
}
while (st.size() && a[st.back()] <= a[i])
st.pop_back();
st.push_back(i);
}
cout << dp[k](n - 1, n - 1);
}
Compilation message
blocks.cpp:7:15: error: conflicting declaration 'int lg [100001]'
int lg[100'001];
^
blocks.cpp:6:11: note: previous declaration as 'const int lg'
const int lg = 16;
^~
blocks.cpp: In member function 'int Sparse::operator()(int, int)':
blocks.cpp:19:29: error: invalid types 'const int[int]' for array subscript
int i = lg[r - l + 1];
^
blocks.cpp: In function 'int main()':
blocks.cpp:29:13: error: invalid types 'const int[int]' for array subscript
lg[i] = __lg(i);
^
