Submission #253573

#	Time	Username	Problem	Language	Result	Execution time	Memory
253573		index_	K blocks (IZhO14_blocks)	C++17	100 / 100	921 ms	6080 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() && a[cur.back()] < a[i]) cur.pop_back();
        if (cur.size()) p[i] = cur.back();
        cur.push_back(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++) {
        vector<li> cur = { 0 };
        for (int i = 1; i <= n; i++) {
            dp2[i] = inf;
            li uk1 = -1, uk2 = cur.size();
            while (uk2 - uk1 > 1) {
                li mid = (uk2 + uk1) / 2;
                if (cur[mid] >= p[i]) uk2 = mid;
                else uk1 = mid;
            }
            if (uk2 != cur.size()) dp2[i] = min(dp2[i], dp1[cur[uk2]] + a[i]);
            while (cur.size() && dp1[cur.back()] > dp1[i]) cur.pop_back();
            cur.push_back(i);
        }
        for (int i = 1; i <= n; i++) {
            dp2[i] = min(dp2[i], dp2[p[i]]);
        }

        for (int i = 0; i <= n; i++) dp1[i] = dp2[i];
    }
    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;
}

Compilation message (stderr)

blocks.cpp: In function 'void solve()':
blocks.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (uk2 != cur.size()) dp2[i] = min(dp2[i], dp1[cur[uk2]] + a[i]);
                 ~~~~^~~~~~~~~~~~~

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