제출 #119734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119734		dolphingarlic	K개의 묶음 (IZhO14_blocks)	C++14	0 / 100	197 ms	4668 KiB

blocks

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int dp[100001][101], segtree[400004], a[100001], n, k;

void build(int node = 1, int l = 1, int r = n) {
    if (l == r)
        segtree[node] = a[l];
    else {
        int 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]);
    }
}

int query(int a, int b, int node = 1, int l = 1, int r = n) {
    if (l > b || r < a || a > b) return 0;
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return max(query(a, b, node * 2, l, mid),
               query(a, b, node * 2 + 1, mid + 1, r));
}

bool case1(int x, int y, int z, int i) {
    return dp[y][i - 1] - dp[x][i - 1] <= query(x + 1, z) - query(y + 1, z);
}

bool case2(int x, int y, int z, int 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)1e8);
    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)) {
                // cout << "YEET " << q[0] << ' ' << q[1] << ' ' << j << '\n';
                q.pop_front();
            }
            int x = q.front();
            // cout << x << ' ';
            dp[j][i] = dp[x][i - 1] + query(x + 1, j);
            while (q.size() > 1 && case2(q[q.size() - 2], q.back(), j, i))
                q.pop_back();
            q.push_back(j);

            // cout << i << ' ' << j << ' ' << dp[j][i] << '\n';
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}

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