Submission #119739

#	Time	Username	Problem	Language	Result	Execution time	Memory
119739		dolphingarlic	K blocks (IZhO14_blocks)	C++14	0 / 100	222 ms	8676 KiB

blocks

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
ll dp[100001][101], segtree[400004], a[100001], n, k;
 
void build(ll node = 1, ll l = 1, ll r = n) {
    if (l == r)
        segtree[node] = a[l];
    else {
        ll mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}
 
ll query(ll a, ll b, ll node = 1, ll l = 1, ll r = n) {
    if (l > b || r < a || a > b) return 0;
    if (l >= a && r <= b) return segtree[node];
    ll mid = (l + r) / 2;
    return max(query(a, b, node * 2, l, mid),
               query(a, b, node * 2 + 1, mid + 1, r));
}
 
bool case1(ll x, ll y, ll z, ll i) {
    return dp[y][i - 1] - dp[x][i - 1] < query(x + 1, z) - query(y + 1, z);
}
 
bool case2(ll x, ll y, ll z, ll i) {
    return dp[y][i - 1] - dp[x][i - 1] + query(y + 1, z) - query(x + 1, z) >
           dp[z][i - 1] - dp[y][i - 1] + query(z + 1, z) - query(y + 1, z);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    FOR(i, 1, n + 1) cin >> a[i];
    build();
 
    FOR(i, 0, n + 1) fill(dp[i], dp[i] + k + 1, INT_MAX);
    dp[0][0] = 0;
 
    FOR(i, 1, k + 1) {
        deque<ll> q;
        q.push_back(i - 1);
        FOR(j, i, n + 1) {
            while (q.size() > 1 && case1(q[0], q[1], j, i)) q.pop_front();
            ll x = q.front();
            dp[j][i] = dp[x][i - 1] + query(x + 1, j);
            while (q.size() > 1 && case2(q[q.size() - 2], q[q.size() - 1], j, i))
                q.pop_back();
            q.push_back(j);
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47