oj.uz

Submission #226316

# Submission time Handle Problem Language Result Execution time Memory
226316 2020-04-23T11:02:39 Z emil_physmath K blocks (IZhO14_blocks) C++17
53 / 100
 1000 ms 228856 KB 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
inline int pow2(int i) { return 1 << i; }
const int maxN = 100'000;
const int lg = 16;
struct Sparse
{
    vector<int> t[lg + 1];
    void initSize(int n)
    {
        for (int i = 0; i <= lg; ++i)
            t[i].resize(n, 1000'000 * 100 + 1);
    }
    void set(int i, int val)
    {
        t[0][i] = val;
        for (int j = 1; j <= lg && pow2(j) <= i + 1; ++j)
            t[j][i] = min(t[j - 1][i], t[j - 1][i - pow2(j - 1)]);
    }
    int operator()(int l, int r)
    {
        int i = __lg(r - l + 1);
        return min(t[i][r], t[i][l + pow2(i) - 1]);
    }
};

Sparse dp[101];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; ++i)
        dp[i].initSize(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    dp[1].set(0, a[0]);
    for (int i = 1; i < n; ++i)
        dp[1].set(i, max(dp[1](i - 1, i - 1), a[i]));
    vector<int> st;
    for (int i = 1; i < n; ++i)
    {
        auto it = upper_bound(st.rbegin(), st.rend(), i, [&a](int i, int j){ return a[i] < a[j]; });
        int m = (it == st.rend() ? -1 : *it);
        for (int j = 2; j <= k; ++j)
        {
            int cur = 1000'000 * k + 1;
            if (m != -1)
                cur = min(cur, dp[j](m, m));
            else
                m = 0;
            if (m < i)
                cur = min(cur, dp[j - 1](m, i - 1) + a[i]);
            dp[j].set(i, cur);
        }
        while (st.size() && a[st.back()] <= a[i])
            st.pop_back();
        st.push_back(i);
    }
    cout << dp[k](n - 1, n - 1);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 1024 KB Output is correct
16 Correct 6 ms 1152 KB Output is correct
17 Correct 5 ms 768 KB Output is correct
18 Correct 6 ms 1024 KB Output is correct
19 Correct 5 ms 1024 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17024 KB Output is correct
2 Correct 18 ms 3840 KB Output is correct
3 Correct 67 ms 21888 KB Output is correct
4 Execution timed out 1036 ms 228856 KB Time limit exceeded
5 Halted 0 ms 0 KB -