Submission #841706

#	Time	Username	Problem	Language	Result	Execution time	Memory
841706		MinaRagy06	K blocks (IZhO14_blocks)	C++17	53 / 100	1047 ms	9428 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl    '\n'
#define ll      long long
#pragma GCC optimize("Ofast")

ll dp[2][100'005];
int a[100'005], sparse[17][100'005], lg[100'005];
void build(int n)
{
    for (int i = 1; i <= n; i++) sparse[0][i] = a[i];
    for (int j = 1; j < 17; j++) for (int i = 1; i + (1 << (j - 1)) <= n; i++) sparse[j][i] = max(sparse[j-1][i], sparse[j-1][i + (1 << (j - 1))]);
}
int query(int l, int r)
{
    int sz = lg[r-l+1];
    return max(sparse[sz][l], sparse[sz][r-(1 << sz) + 1]);
}
int n, m;
int mstanyeh(int lvl, int j, int k)
{
    int l = max(j + 1, k + 1), r = n;
    while (l <= r)
    {
        int md = ((l + r) >> 1);
        if (dp[lvl & 1][j] - dp[lvl & 1][k] <= query(k + 1, md) - query(j + 1, md)) r = md - 1;
        else l = md + 1;
    }
    return l;
}
signed main()
{
    lesgooo;
    lg[1] = 0;
    for (int i = 2; i < 100'005; i++) lg[i] = lg[i >> 1] + 1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(n);
    for (int i = 1; i <= n; i++) dp[0][i] = query(1, i);
    dp[0][0] = dp[1][0] = 1e18;
    for (int i = 1; i < m; i++)
    {
        vector<int> v;
        for (int j = 1; j <= n; j++)
        {
            while (v.size() > 1 && mstanyeh(i - 1, v[v.size() - 2], v.back()) <= mstanyeh(i - 1, v.back(), j - 1)) v.pop_back();
            v.push_back(j - 1);
            while (v.size() > 1 && mstanyeh(i - 1, v[v.size() - 2], v.back()) <= j) v.pop_back();
            dp[i&1][j] = dp[(i - 1)&1][v.back()] + query(v.back() + 1, j);
        }
    }
    cout << dp[(m - 1) & 1][n] << endl;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47