oj.uz

Submission #887464

# Submission time Handle Problem Language Result Execution time Memory
887464 2023-12-14T15:07:06 Z Perl32 Stove (JOI18_stove) C++14
100 / 100
 871 ms 7728 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INFL = (ll) 1e13 + 1e9;

struct SegTree {
    struct Node {
        ll v = INFL, c = 0;

        Node() = default;
        Node(ll v, ll c) : v(v), c(c) {}
    };

    vector<Node> t;
    int sz;

    SegTree(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.resize(sz << 1);
    }

    Node merge(const Node &fir, const Node &sec) {
        if (fir.v < sec.v || (fir.v == sec.v && fir.c < sec.c)) {
            return fir;
        }
        return sec;
    }

    void upd(int i, Node v, int x, int lx, int rx) {
        if (lx + 1 == rx) {
            t[x] = v;
            return;
        }
        int m = (lx + rx) >> 1;
        if (i < m) {
            upd(i, v, x << 1, lx, m);
        } else {
            upd(i, v, x << 1 | 1, m, rx);
        }
        t[x] = merge(t[x << 1], t[x << 1 | 1]);
    }

    void upd(int i, Node v) {
        upd(i, v, 1, 0, sz);
    }

    Node get(int l, int r, int x, int lx, int rx) {
        if (rx <= l || r <= lx) {
            return Node();
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int m = (lx + rx) >> 1;
        return merge(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx));
    }

    Node get(int l, int r) {
        return get(l, r, 1, 0, sz);
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    a[0] = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    SegTree st(n + 1);
    auto solve = [&](ll p) -> pair<ll, int> {
        vector<pair<ll, int>> dp(n + 1);
        dp[0] = {0, 0};
        st.upd(0, {0, 0});
        for (int i = 1; i <= n; ++i) {
            auto [v, c] = st.get(0, i);
            dp[i] = {dp[i - 1].first + 1 + p, dp[i - 1].second + 1};
            dp[i] = min(dp[i], {a[i] + 1 + v + p, c + 1});
            st.upd(i, {-a[i] + dp[i - 1].first, dp[i - 1].second});
        }
        return dp[n];
    };
    ll lx = -INFL, rx = INFL;
    while (lx + 1 < rx) {
        ll m = (lx + rx) >> 1;
        if (solve(m).second > k) {
            lx = m;
        } else {
            rx = m;
        }
    }
    auto [v, c] = solve(rx);
    cout << v - rx * k;
}

/*

 */

Compilation message

stove.cpp: In lambda function:
stove.cpp:83:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |             auto [v, c] = st.get(0, i);
      |                  ^
stove.cpp: In function 'int main(int32_t, char**)':
stove.cpp:99:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |     auto [v, c] = solve(rx);
      |          ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 19 ms 604 KB Output is correct
11 Correct 19 ms 604 KB Output is correct
12 Correct 22 ms 600 KB Output is correct
13 Correct 18 ms 604 KB Output is correct
14 Correct 20 ms 604 KB Output is correct
15 Correct 17 ms 600 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 19 ms 604 KB Output is correct
11 Correct 19 ms 604 KB Output is correct
12 Correct 22 ms 600 KB Output is correct
13 Correct 18 ms 604 KB Output is correct
14 Correct 20 ms 604 KB Output is correct
15 Correct 17 ms 600 KB Output is correct
16 Correct 833 ms 6508 KB Output is correct
17 Correct 871 ms 7476 KB Output is correct
18 Correct 827 ms 7728 KB Output is correct
19 Correct 810 ms 7476 KB Output is correct
20 Correct 808 ms 7476 KB Output is correct
21 Correct 777 ms 7484 KB Output is correct
22 Correct 761 ms 7476 KB Output is correct
23 Correct 765 ms 7476 KB Output is correct
24 Correct 803 ms 7476 KB Output is correct