oj.uz

Submission #871952

# Submission time Handle Problem Language Result Execution time Memory
871952 2023-11-12T03:51:48 Z sleepntsheep K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 2396 KB 
#include <iostream>
#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], t[N<<1];
u64 dp[2][N];

inline int qry(int l, int r)
{
    int z = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
    {
        if (l&1) z=max(z, t[l++]);
        if (r&1) z=max(t[--r], z);
    }
    return z;
}

void combine(int i, int l, int r, int optl, int optr)
{
    if (l > r) return;
    int m = (l+r)/2;
    //if (m <= i - 1) return;
    pair<u64, int> best = {1e18, -1};
    for (int j = max(optl, i-1); j <= m && j <= optr; ++j)
        best = min(best, {(j ? dp[(i&1)^1][j-1] : 0) + qry(j, m), j});
    dp[i&1][m] = best.first;
    combine(i, l, m-1, optl, best.second);
    combine(i, m+1, r, best.second, optr);
}

int main()
{
    ShinLena;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i], t[i+n] = a[i];
    for (int i = n; i--;) t[i] = max(t[i<<1], t[i<<1|1]);
    for (int i = 1; i <= k; ++i) 
    {
        memset(dp[i&1], 63, sizeof *dp);
        combine(i, 0, n-1, 0, n-1);
    }
    cout << dp[k&1][n-1];
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -