1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef int64_t ll;
constexpr ll N = 300025, INF = 1e18;

struct BIT {
    pair<ll,int> mn[N];
    int n;
    void init(int _n) {
        n = _n;
        for(int i = 1; i <= n; i++) mn[i] = {INF, 0};
    }
    void edit(int p, pair<ll,int> d) {
        for(; p <= n; p += p&-p) mn[p] = min(mn[p], d);
    }
    pair<ll,int> query(int p) {
        pair<ll,int> res = {INF, 0};
        for(; p > 0; p -= p&-p) res = min(res, mn[p]);
        return res;
    }
} pre, suf;
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    // dp[i] = min{dp[j] + max(v[i] - v[j], 0)};
    // dp[i] = min{v[i] + dp[j]-v[j] | v[i] >= v[j]}, min{dp[j] | v[i] < v[j]}
    // dp[1] = {0, 0}
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for(int &x: h) cin >> x;
    vector<int> u = h;
    sort(u.begin(), u.end()), u.erase(unique(u.begin(), u.end()), u.end());
    for(int &x: h) x = lower_bound(u.begin(), u.end(), x) - u.begin() + 1;
    pre.init(u.size());
    suf.init(u.size());
    pre.edit(h[0], {-h[0], 0});
    suf.edit(u.size()+1-h[0], {0, 0});
    pair<ll,int> dp;
    for(int i = 1; i < n; i++) {
        pair<ll,int> a = pre.query(h[i]), b = suf.query(u.size()-h[i]);
        a.ff += h[i];
        dp = min(a,b);
        dp.ss -= 1;
        suf.edit(u.size()+1-h[i], dp);
        dp.ff -= h[i];
        pre.edit(h[i], dp);
    }
    cout << min(m, -dp.ss) << '\n';
}