oj.uz

Submission #659820

# Submission time Handle Problem Language Result Execution time Memory
659820 2022-11-19T10:37:04 Z stevancv K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int inf = 2e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> gr(n);
    stack<int> s;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] < a[i]) s.pop();
        if (!s.empty()) gr[s.top()].push_back(i);
        else v.push_back(i);
        s.push(i);
    }
    while (!s.empty()) s.pop();
    vector<int> dp(n + 1, inf);
    dp[0] = 0;
    while (k--) {
        vector<int> f(n, inf), g(n, inf);
        for (int i = 0; i < n; i++) {
            while (!s.empty() && a[s.top()] <= a[i]) {
                smin(f[i], min(f[s.top()], dp[s.top()]));
                s.pop();
            }
            if (s.empty()) smin(f[i], dp[0]);
            s.push(i);
        }
        while (!s.empty()) s.pop();
        queue<int> q;
        for (int i : v) q.push(i);
        while (!q.empty()) {
            int s = q.front(); q.pop();
            for (int u : gr[s]) {
                g[u] = min(g[s], dp[s]);
                q.push(u);
            }
        }
        for (int i = 0; i <= n; i++) dp[i] = inf;
        for (int i = 1; i <= n; i++) {
            dp[i] = min(f[i - 1], g[i - 1]) + a[i - 1];
        }
    }
    int ans = inf;
    int mx = -inf;
    for (int i = n - 1; i >= 0; i--) {
        smax(mx, a[i]);
        if (a[i] == mx) smin(ans, dp[i + 1]);
    }
    cout << ans << en;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -