oj.uz

Submission #932492

# Submission time Handle Problem Language Result Execution time Memory
932492 2024-02-23T13:53:51 Z andrew K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>


using namespace std;
typedef long long ll;


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    
    vector <ll> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }    

    vector <vector <ll>> dp(k + 1, vector <ll> (n, 1e15));

    dp[1][0] = a[0];
    ll mx = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] < mx) continue;
        dp[1][i] = a[i];
        mx = a[i];
    }

    for (int step = 2; step <= k; step++) {
        vector <ll> u(n, 1e15);
        vector <int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && a[st.back()] <= a[i]) {
                u[i] = min(u[i], u[st.back()]);
                u[i] = min(u[i], dp[step - 1][st.back()]);
                st.pop_back();
            }
            dp[step][i] = min(dp[step][i], u[i] + a[i]);
            if (!st.empty()) {
                dp[step][i] = min(dp[step][i], dp[step - 1][st.back()] + a[i]);
            }
            if (st.size() > 1) {
                dp[step][i] = min(dp[step][i], dp[step - 1][st[st.size() - 2]] + a[i]);
            }
            st.push_back(i);            
        }
    }   

    ll ans = dp[k][n - 1];
    mx = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        if (mx > a[i]) continue;
        ans = min(ans, dp[k][i]);
        mx = a[i];
    }

    cout << ans << "\n";
    
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -