Submission #1082237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082237		meowww	K blocks (IZhO14_blocks)	C++17	100 / 100	150 ms	82004 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1ll)
#define cntbit(x) __builtin_popcount(x)
#define int long long
#define vi vector <int>
#define vb vector <bool>
#define vvi vector <vector <int>>
#define fi first
#define se second
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define all(x) x.begin(), x.end()
 
const int oo = 1e9;
 
main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vi a(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vvi dp(k + 1, vi(n + 1, oo));
    dp[0][0] = 0;
    
    for (int i = 1; i <= k; i++) {
        stack <pii> st;
        for (int j = i - 1; j < n; j++) {
            int mini = dp[i - 1][j];
            
            while (!st.empty() && a[st.top().fi] <= a[j]) {
                mini = min(mini, st.top().se);
                st.pop();
            }
            
            if (st.empty() || a[j] + mini < a[st.top().fi] + st.top().se) {
                st.emplace(j, mini);
            }
            
            dp[i][j + 1] = a[st.top().fi] + st.top().se;
        }
    }
    
    cout << dp[k][n] << '\n';
    
    return 0;
}

Compilation message (stderr)

blocks.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main() {
      | ^~~~

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