Submission #955877

#	Time	Username	Problem	Language	Result	Execution time	Memory
955877		gaoxam123	K blocks (IZhO14_blocks)	C++14	100 / 100	151 ms	43100 KiB

blocks

// https://oj.uz/problem/view/IZhO14_blocks
#include <bits/stdc++.h>
using namespace std;

int N, K;
int a[100005], dp[105][100005], L[100005];

// int main() {
//     cin >> N >> K;
//     memset(dp, 1000000, sizeof(dp));
//     for(int i = 1; i <= N; i ++) {
//         cin >> a[i];
//     }
//     // THIS VERSION IS NOT OPTIMIZED, BUT WORKS PROPERLY
//     for(int i = 1; i <= K; i ++) {
//         for(int j = i; j <= N; j ++) {
//             if(i == 1) {
//                 if(j == 1) {
//                     dp[i][j] = a[j];
//                 }
//                 else {
//                     dp[i][j] = max(dp[i][j - 1], a[j]);
//                 }
//             }
//             else if(i == j) {
//                 dp[i][j] = dp[i - 1][j - 1] + a[j];
//             }
//             else {
//                 int mx = a[j];
//                 for(int k = j - 1; k >= i - 1; k --) {
//                     dp[i][j] = min(dp[i][j], dp[i - 1][k] + mx);
//                     mx = max(mx, a[k]);
//                 }
//             }       
//         }
//     }
//     cout << dp[K][N];
// }

int main() {
    cin >> N >> K;
    memset(dp, 1000000, sizeof(dp));
    for(int i = 1; i <= N; i ++) {
        cin >> a[i];
    }  
    dp[1][0] = 0;
    for(int i = 1; i <= N; i ++) {
        dp[1][i] = max(dp[1][i - 1], a[i]);
    }
    for(int i = 2; i <= K; i ++) {
        stack <pair <int, int> > st;
        for(int j = i; j <= N; j ++) {
            int minDP = dp[i - 1][j - 1];
            while(!st.empty() && a[st.top().second] <= a[j]) {
                minDP = min(minDP, st.top().first);
                st.pop();
            }
            dp[i][j] = min(minDP + a[j], dp[i][st.empty() ? 0 : st.top().second]);
            st.push(make_pair(minDP, j));
        }
    }
    cout << dp[K][N];
}

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