oj.uz

답안 #891095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891095 2023-12-22T07:34:44 Z The_Samurai K개의 묶음 (IZhO14_blocks) C++17
0 / 100
 0 ms 456 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int inf = 1e9;

template<typename T> struct SegTree {
    vector<T> tree;
    int size;
    T neutral_element = 1e9; // sum - 0, mx - (-INF), mn - INF

    inline T merge(T a, T b) {
        return min(a, b);
    }

    void init(int n) {
        size = 1;
        while (size <= n) size *= 2;
        tree.assign(2 * size, neutral_element);
    }

    void build(vector<T> &a) {
        size = 1;
        while (size < a.size()) size *= 2;
        tree.assign(2 * size, neutral_element);
        for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
        for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
    }

    void set(int p, T value) {  // set value at position p
        p += size;
        tree[p] = merge(value, tree[p]);
        for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]);
    }

    T get(int l, int r) {  // sum on interval [l, r]
        if (l > r) return neutral_element;
        T res = neutral_element;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = merge(res, tree[l++]);
            if (r & 1) res = merge(res, tree[--r]);
        }
        return res;
    }
};


void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), left(n + 1), right(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    {
        stack<int> st;
        for (int i = 1; i <= n; i++) {
            while (!st.empty() and a[i] > a[st.top()]) st.pop();
            left[i] = st.empty() ? 0 : st.top();
            st.push(i);
        }
        while (!st.empty()) st.pop();
        for (int i = n; i > 0; i--) {
            while (!st.empty() and a[i] > a[st.top()]) st.pop();
            right[i] = st.empty() ? n + 1 : st.top();
            st.push(i);
        }
    }
    SegTree<int> last; last.init(n + 1);
    last.set(0, 0);
    for (int len = 1; len <= k; len++) {
        vector<vector<int>> out(n + 1);
        multiset<int, greater<>> st;
        SegTree<int> sg; sg.init(n + 1);
        for (int i = 1; i <= n; i++) {
            int x = last.get(left[i], i - 1) + a[i];
            out[right[i] - 1].emplace_back(x);
            st.insert(x);
            sg.set(i, *st.begin());
            for (int x: out[i]) st.erase(st.find(x));
        }
        last = sg;
    }
    cout << last.get(n, n);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -