oj.uz

Submission #873027

# Submission time Handle Problem Language Result Execution time Memory
873027 2023-11-14T10:22:43 Z sleepntsheep K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 3216 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

int n, k, a[N];
i64 dp[2][N], t[N<<1];
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

inline __attribute__((always_inline)) 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, z = a[0]; i < n; ++i) cin >> a[i], z = max(z, a[i]), dp[0][i] = t[i+n] = z;
    for (int i = n; i--;) t[i] = std::min(t[i<<1], t[i<<1|1]);

    for (int j = 1; j < k; ++j)
    {
        stack<int> q;
        for (int i = 0; i < n; ++i)
        {
            while (q.size() && a[q.top()] <= a[i]) q.pop();
            i64 &d = dp[j&1][i];

            if (q.size())
                d = min({d, dp[j&1][q.top()], dp[j&1^1][q.top()] + a[i], qry(q.top() + 1, i-1) + a[i]});
            else
                dp[j&1][i] = qry(0, i-1) + a[i];

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

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

    return 0;
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:54:51: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   54 |                 d = min({d, dp[j&1][q.top()], dp[j&1^1][q.top()] + a[i], qry(q.top() + 1, i-1) + a[i]});
      |                                                  ~^~
blocks.cpp:64:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   64 |     cout << dp[k&1^1][n-1];
      |                ~^~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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