제출 #253564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253564		index_	K개의 묶음 (IZhO14_blocks)	C++17	0 / 100	3 ms	1024 KiB

blocks

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <chrono>
#include <cassert>
#include <bitset>
#include <random>

using namespace std;

typedef long long li;
typedef  long double ld;
const li MAX = 3e5 + 20;

li inf = (li)1e15;
li mod = (li)998244353;

li dp1[MAX], dp2[MAX], p[MAX], cool[MAX];
li n, k, a[MAX];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<li> cur;
    for (int i = 1; i <= n; i++) {
        while (cur.size() && cur.back() < a[i]) cur.pop_back();
        if (cur.size()) p[i] = cur.back();
        cur.push_back(a[i]);
    }
    li cur_max = a[1];
    dp1[0] = inf;
    dp2[0] = inf;
    for (int i = 1; i <= n; i++) {
        cur_max = max(cur_max, a[i]);
        dp1[i] = cur_max;
    }

    for (int j = 2; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            cool[i] = 0;
            if (dp1[p[i]] == inf) cool[i] = 1;
            else dp2[i] = dp1[p[i]];
        }
        li cur_min = dp1[j - 1];
        for (int i = j; i <= n; i++) {
            if (cool[i]) dp2[i] = cur_min + a[i];
            cur_min = min(cur_min, dp1[i]);
        }

        for (int i = 1; i <= n; i++) {
            dp1[i] = dp2[i];
            dp2[i] = 0;
        }
    }

    cout << dp1[n];
}

int main() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios::sync_with_stdio(0);
    li q;
    q = 1;
    while (q--) solve();

    return 0;
}

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