Submission #1269563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269563		lechaa	K개의 묶음 (IZhO14_blocks)	C++20	53 / 100	1090 ms	165136 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<int>> s(k+5);
    vector<vector<pair<int, int>>> st(n+2);
    dp[0][1] = 0;
    for(int i = 0; i <= n; i++){
        for(auto i : st[i]){
            s[i.first].erase(s[i.first].find(i.second));
        }
        for(int y = k+1; y >= 1; y--){
            if(s[y].size() > 0){
                dp[i][y] = min(*s[y].begin(), 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]);
            st[r[i]+1].push_back({y+1, dp[i][y] + x[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