Submission #1266747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266747		flaming_top1	K blocks (IZhO14_blocks)	C++20	100 / 100	158 ms	81068 KiB

blocks

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 1e15;

using namespace std;

int n, k;
lint a[100005], dp[105][100005];

fami lore()
{
    SPED;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        dp[1][i] = max(dp[1][i - 1], a[i]);
    for (int i = 2; i <= k; i++)
    {
        vector<pair<lint, int>> st;
        for (int j = i; j <= n; j++)
        {
            lint cur = dp[i - 1][j - 1];
            while (!st.empty() and a[st.back().se] <= a[j])
            {
                cur = min(cur, st.back().fi);
                st.pop_back();
            }
            lint temp = st.empty() ? INF : dp[i][st.back().se];
            dp[i][j] = min(cur + a[j], temp);
            st.emplace_back(cur, j);
        }
        st.clear();
    }
    cout << dp[k][n];
}
// Let your soul wander where dreams are born.

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