oj.uz

Submission #873018

# Submission time Handle Problem Language Result Execution time Memory
873018 2023-11-14T10:10:34 Z sleepntsheep K blocks (IZhO14_blocks) C++17
0 / 100
 20 ms 80916 KB 
#include <iostream>
#include <stack>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 100000


template <typename T, const T& (*F)(const T&, const T&)>
struct opstack
{
    deque<pair<T, T>> a;

    size_t size() { return a.size(); }
    bool empty() { return a.empty(); }

    void push(T x)
    {
        if (size()) a.push_back({x, F(a.back().second, x)});
        else a.push_back({x, x});
    }

    T top() { return a.back().first; }
    T op() { return a.back().second; }
    void pop() { a.pop_back(); }
    void swap(opstack &x) { a.swap(x.a); }

};

template <typename T, const T& (*F)(const T&, const T&)>
struct opdeque
{
    opstack<T, F> f, b, t;

    void rebalance()
    {
        bool s = false;
        if (b.empty()) { s = true; b.swap(f); }
        int y = (b.size() / 2);
        while (y--) { t.push(b.top()); b.pop(); }
        while (b.size()) { f.push(b.top()); b.pop(); }
        while (t.size()) { b.push(t.top()); t.pop(); }
        if (s) b.swap(f);
    }

    size_t size() { return b.size() + f.size(); }
    bool empty() { return size() == 0; }
    void push_front(T x) { f.push(x); }
    void push_back(T x) { b.push(x); }
    T back()
    {
        if (b.empty()) rebalance();
        return b.top();
    }
    T front()
    {
        if (f.empty()) rebalance();
        return f.top();
    }
    void pop_back()
    {
        if (b.empty()) rebalance();
        b.pop();
    }
    void pop_front()
    {
        if (f.empty()) rebalance();
        f.pop();
    }
    T op()
    {
        if (f.empty()) return b.op();
        if (b.empty()) return f.op();
        return F(b.op(), f.op());
    }
};

int n, k, a[N];
i64 dp[N][101], t[N<<1];

i64 qry(int l, int r)
{
    i64 z = 1e18;
    for (l += n, r += n + 1; l < r; l >>= 1, r>>=1)
    {
        if (l&1) z = min(z, t[l++]);
        if (r&1) z = min(t[--r], z);
    }
    return z;
}

int main()
{
    memset(dp, 63, sizeof dp);
    ShinLena;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];

    {
        opstack<int, std::max> q;
        for (int i = 0; i < n; ++i) q.push(a[i]), dp[0][i] = q.op();
    }

    for (int j = 1; j < k; ++j)
    {
        stack<int> q;
        opdeque<int, std::min> y;
        for (int i = 0; i < n; ++i)
        {
            while (q.size() && a[q.top()] <= a[i]) q.pop();

            if (q.size())
            {
                auto C = min(dp[j][q.top()], dp[j-1][q.top()] + a[i]);
                C = min(C, qry(q.top() + 1, i-1) + a[i]);
                dp[j][i] = C;
            }
            else if (y.size())
            {
                dp[j][i] = y.op() + a[i];
            }

            y.push_back(dp[j-1][i]);
            q.push(i);
        }
        for (int i = 0; i < n; ++i) t[i+n] = dp[j][i];
        for (int i = n; i--;) t[i] = std::min(t[i<<1], t[i<<1|1]);
    }

    cout << dp[k-1][n-1];

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 80892 KB Output is correct
2 Correct 11 ms 80732 KB Output is correct
3 Correct 11 ms 80732 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80696 KB Output is correct
6 Correct 10 ms 80732 KB Output is correct
7 Correct 10 ms 80916 KB Output is correct
8 Incorrect 10 ms 80732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 80892 KB Output is correct
2 Correct 11 ms 80732 KB Output is correct
3 Correct 11 ms 80732 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80696 KB Output is correct
6 Correct 10 ms 80732 KB Output is correct
7 Correct 10 ms 80916 KB Output is correct
8 Incorrect 10 ms 80732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 80892 KB Output is correct
2 Correct 11 ms 80732 KB Output is correct
3 Correct 11 ms 80732 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80696 KB Output is correct
6 Correct 10 ms 80732 KB Output is correct
7 Correct 10 ms 80916 KB Output is correct
8 Incorrect 10 ms 80732 KB Output isn't correct
9 Halted 0 ms 0 KB -