//Suleyman Atayew
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define N 100010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <int, int>
using namespace std;
int n, k;
int v[N];
int MX[N];
int T[N*4];
int L[N*4];
int dp[110][N];
void init(int l, int r, int node)
{
L[node] = 0;
T[node] = 1e9;
if(l == r) return;
init(l, (l+r)/2, node*2);
init((l+r)/2+1, r, node*2+1);
}
void upd2(int x, int y, int l, int r, int node)
{
if(l == r) {
T[node] = dp[x][l];
return;
}
if(y <= (l+r)/2)
upd2(x, y, l, (l+r)/2, node*2);
else
upd2(x, y, (l+r)/2+1, r, node*2+1);
T[node] = min(T[node*2], T[node*2+1]);
if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
else L[node] = L[node*2+1];
}
shift(int node, int to)
{
T[to] -= L[to];
T[to] += L[node];
L[to] = L[node];
}
void upd(int a, int b, int x, int l, int r, int node)
{
if(l > b || r < a) return;
if(l >= a && r <= b) {
if(l == r) {
T[node] -= L[node];
T[node] += x;
L[node] = x;
return;
}
L[node] = x;
shift(node, node*2);
shift(node, node*2+1);
T[node] = min(T[node*2], T[node*2+1]);
if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
else L[node] = L[node*2+1];
return;
}
shift(node, node*2);
shift(node, node*2+1);
L[node] = 0;
upd(a, b, x, l, (l+r)/2, node*2);
upd(a, b, x, (l+r)/2+1, r, node*2+1);
T[node] = min(T[node*2], T[node*2+1]);
if(T[node*2] < T[node*2+1]) L[node] = L[node*2];
else L[node] = L[node*2+1];
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> v[i];
vector <int> E;
for(int i = 1; i <= n; i++) {
while(!E.empty() && v[E.back()] < v[i])
E.pop_back();
if(E.empty()) MX[i] = 0;
else {
if(v[E.back()] == v[i]) MX[i] = MX[E.back()];
else MX[i] = E.back()+1;
}
E.pb(i);
}
for(int i = 1; i <= n; i++) dp[0][i] = 1e9;
for(int i = 1; i <= k; i++) {
init(0, n, 1);
for(int h = 0; h <= n; h++) {
if(h < i) {
dp[i][h] = 1e9;
upd2(i-1, h, 0, n, 1);
continue;
}
upd(MX[h], h-1, v[h], 0, n, 1);
dp[i][h] = T[1];
// cout << T[1] << " ------------\n";
//
// if(i == 2) {
// for(int h = 1; h <= 13; h++) cout << T[h] << " " << L[h] << "\n";
// cout << "\n";
// }
upd2(i-1, h, 0, n, 1);
// if(i == 2) {
// for(int h = 1; h <= 13; h++) cout << T[h] << " " << L[h] << "\n";
// cout << "\n";
// }
}
}
cout << dp[k][n];
}
Compilation message
blocks.cpp:58:23: error: ISO C++ forbids declaration of 'shift' with no type [-fpermissive]
shift(int node, int to)
^
blocks.cpp: In function 'int shift(int, int)':
blocks.cpp:63:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
