#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define md ((l + r) >> 1)
#pragma GCC optimize("Ofast,O3")
ll dp[2][100'005];
int a[100'005], sparse[17][100'005], lg[100'005];
void build(int n)
{
for (int i = 1; i <= n; i++) sparse[0][i] = a[i];
for (int j = 1; j < 17; j++) for (int i = 1; i + (1 << (j - 1)) <= n; i++) sparse[j][i] = max(sparse[j-1][i], sparse[j-1][i + (1 << (j - 1))]);
}
int query(int l, int r)
{
int sz = lg[r-l+1];
return max(sparse[sz][l], sparse[sz][r-(1 << sz) + 1]);
}
int n, m;
int mstanyeh(int lvl, int j, int k)
{
if (dp[lvl & 1][j] - dp[lvl & 1][k] > query(k + 1, n) - query(j + 1, n)) return n + 1;
int l = max(j + 1, k + 1), r = n;
while (l <= r)
{
dp[lvl & 1][j] - dp[lvl & 1][k] <= query(k + 1, md) - query(j + 1, md)? r = md - 1 : l = md + 1;
}
return l;
}
int v[100'005], mstany[100'005], vsz, mstanysz, val;
signed main()
{
init_output();
lg[1] = 0;
for (int i = 2; i < 100'005; i++) lg[i] = lg[i >> 1] + 1;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(n);
for (int i = 1; i <= n; i++) dp[0][i] = query(1, i);
dp[0][0] = dp[1][0] = 1e18;
for (int i = 1; i < m; i++)
{
vsz = mstanysz = 0;
for (int j = 1; j <= n; j++)
{
while (vsz > 1 && mstany[mstanysz-1] <= (val = mstanyeh(i - 1, v[vsz-1], j - 1))) vsz--, mstanysz--;
if (vsz == 1) val = mstanyeh(i - 1, v[vsz-1], j - 1);
v[vsz++] = j - 1;
if (vsz > 1) mstany[mstanysz++] = val;
while (vsz > 1 && mstany[mstanysz-1] <= j) vsz--, mstanysz--;
dp[i&1][j] = dp[(i - 1)&1][v[vsz-1]] + query(v[vsz-1] + 1, j);
}
}
cout << dp[(m - 1) & 1][n];
return 0;
}
Compilation message
blocks.cpp: In function 'int main()':
blocks.cpp:34:5: error: 'init_output' was not declared in this scope
34 | init_output();
| ^~~~~~~~~~~
