oj.uz

Submission #872741

# Submission time Handle Problem Language Result Execution time Memory
872741 2023-11-13T16:22:48 Z sleepntsheep K blocks (IZhO14_blocks) C++17
18 / 100
 13 ms 79704 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<pair<int, int>, std::min> 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())
            {
                auto C = min(dp[j][q.back()], dp[j-1][q.back()] + a[i]);
                while (w.size() && w.front().second < q.back()) w.pop_front();
                if (w.size()) 
                {
                    C = min(C, 1ll * w.op().first + a[i]);
                }
                dp[j][i] = C;
            }
            else if (y.size())
            {
                dp[j][i] = y.op() + a[i];
            }

            w.push_back({dp[j-1][i], i});
            y.push_back(dp[j-1][i]);
            q.push_back(i);
        }
    }

    for (int j = 0; j < k; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            //cout << dp[j][i] << "   ";
        }
        //cout<<endl;
    }

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

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 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 79348 KB Output is correct
6 Correct 10 ms 79452 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 9 ms 79316 KB Output is correct
9 Correct 9 ms 79448 KB Output is correct
10 Correct 10 ms 79452 KB Output is correct
11 Correct 9 ms 79460 KB Output is correct
12 Correct 10 ms 79452 KB Output is correct
13 Incorrect 10 ms 79332 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
18.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 11 ms 79452 KB Output is correct
6 Correct 11 ms 79448 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 10 ms 79452 KB Output is correct
9 Correct 10 ms 79452 KB Output is correct
10 Correct 9 ms 79452 KB Output is correct
11 Correct 10 ms 79452 KB Output is correct
12 Correct 9 ms 79704 KB Output is correct
13 Correct 9 ms 79492 KB Output is correct
14 Correct 10 ms 79452 KB Output is correct
15 Correct 9 ms 79520 KB Output is correct
16 Correct 10 ms 79452 KB Output is correct
17 Correct 10 ms 79512 KB Output is correct
18 Correct 9 ms 79452 KB Output is correct
19 Correct 9 ms 79448 KB Output is correct
20 Correct 9 ms 79704 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 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 79348 KB Output is correct
6 Correct 10 ms 79452 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 9 ms 79316 KB Output is correct
9 Correct 9 ms 79448 KB Output is correct
10 Correct 10 ms 79452 KB Output is correct
11 Correct 9 ms 79460 KB Output is correct
12 Correct 10 ms 79452 KB Output is correct
13 Incorrect 10 ms 79332 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 13 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 79348 KB Output is correct
6 Correct 10 ms 79452 KB Output is correct
7 Correct 10 ms 79452 KB Output is correct
8 Correct 9 ms 79316 KB Output is correct
9 Correct 9 ms 79448 KB Output is correct
10 Correct 10 ms 79452 KB Output is correct
11 Correct 9 ms 79460 KB Output is correct
12 Correct 10 ms 79452 KB Output is correct
13 Incorrect 10 ms 79332 KB Output isn't correct
14 Halted 0 ms 0 KB -