oj.uz

Submission #872734

# Submission time Handle Problem Language Result Execution time Memory
872734 2023-11-13T16:05:04 Z sleepntsheep K blocks (IZhO14_blocks) C++17
0 / 100
 16 ms 79464 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];

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

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

    for (int j = 1; j < k; ++j)
    {
        opdeque<int, std::max> q;
        opdeque<int, std::max> w;
        opdeque<int, std::min> y;
        for (int i = 0; i < n; ++i)
        {
            while (q.size() && a[q.back()] < a[i])
            {
                q.pop_back();
                if (q.size()) w.pop_back();
            }

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

            y.push_back(dp[j-1][i]);
            q.push_back(i);

        }
    }

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

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 79452 KB Output is correct
2 Correct 10 ms 79344 KB Output is correct
3 Correct 10 ms 79352 KB Output is correct
4 Correct 10 ms 79336 KB Output is correct
5 Correct 10 ms 79452 KB Output is correct
6 Correct 10 ms 79460 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 10 ms 79304 KB Output is correct
9 Correct 10 ms 79452 KB Output is correct
10 Correct 10 ms 79452 KB Output is correct
11 Incorrect 10 ms 79288 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 79452 KB Output is correct
2 Correct 10 ms 79344 KB Output is correct
3 Correct 10 ms 79352 KB Output is correct
4 Correct 10 ms 79336 KB Output is correct
5 Correct 10 ms 79452 KB Output is correct
6 Correct 10 ms 79460 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 10 ms 79304 KB Output is correct
9 Correct 10 ms 79452 KB Output is correct
10 Correct 10 ms 79452 KB Output is correct
11 Incorrect 10 ms 79288 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 79452 KB Output is correct
2 Correct 10 ms 79344 KB Output is correct
3 Correct 10 ms 79352 KB Output is correct
4 Correct 10 ms 79336 KB Output is correct
5 Correct 10 ms 79452 KB Output is correct
6 Correct 10 ms 79460 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 10 ms 79304 KB Output is correct
9 Correct 10 ms 79452 KB Output is correct
10 Correct 10 ms 79452 KB Output is correct
11 Incorrect 10 ms 79288 KB Output isn't correct
12 Halted 0 ms 0 KB -