Submission #1269564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269564		lechaa	K blocks (IZhO14_blocks)	C++20	53 / 100	1104 ms	141992 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("blocks.in", "r", stdin);
	// freopen("blocks.out", "w", stdout);
    int n, k; cin >> n >> k;
    vector<int> x(n);
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    x.push_back(-1e9);
    vector<int> r(n+1, n);
    stack<int> g;
    for(int i = n-1; i >= 0; i--){
        while(g.size() > 0){
            if(x[g.top()] <= x[i]){
                g.pop();
            }else{
                break;
            }
        }
        if(g.size() > 0){
            r[i] = g.top();
        }
        g.push(i);
    }
    vector<vector<int>> dp(n+1, vector<int>(k+5, 1e9));
    vector<multiset<pair<int, int>>> s(k+5);
    dp[0][1] = 0;
    for(int i = 0; i <= n; i++){
        for(int y = k+1; y >= 1; y--){
            while(s[y].size() > 0){
                if(s[y].begin()->second < i){
                    s[y].erase(s[y].begin());
                }else{
                    break;
                }
            }
            if(s[y].size() > 0){
                dp[i][y] = min(s[y].begin()->first, dp[i][y]);
            }
            if(i == n) continue;
            if(r[i] != n){
                dp[r[i]][y] = min(dp[r[i]][y], dp[i][y]); 
            }
            s[y+1].insert({dp[i][y] + x[i], r[i]});
        }
    }
    cout << dp[n][k+1] << "\n";
    return 0;
}

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