Submission #1165354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165354		DangKhoizzzz	K blocks (IZhO14_blocks)	C++20	100 / 100	392 ms	81184 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int maxn = 1e5 + 7;

struct Fenwick_Tree_Min
{
    vector <int> tree;
    void init(int n) {tree.assign(n+4 , INF);}

    void update(int pos , int val)
    {
        pos = (int)(tree.size()) - pos;
        while(pos < (int)tree.size())
        {
            tree[pos] = min(tree[pos] , val);
            pos += (pos & (-pos));
        }
    }

    int get_suf(int pos)
    {
        pos = tree.size() - pos;
        int res = INF;
        while(pos > 0)
        {
            res = min(tree[pos] , res);
            pos -= (pos & (-pos));
        }
        return res;
    }
};

Fenwick_Tree_Min BIT[102];

int n , k , a[maxn] , Lnxt[maxn] , Rnxt[maxn] , dp[maxn][102];

void build()
{
    for(int i = 0; i <= k; i++) BIT[i].init(n);

    stack <int> st;

    for(int i = 1; i <= n; i++)
    {
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(st.empty()) Lnxt[i] = 0;
        else Lnxt[i] = st.top();
        st.push(i);
    }

    while(!st.empty()) st.pop();

    for(int i = n; i >= 1; i--)
    {
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(st.empty()) Rnxt[i] = n+1;
        else Rnxt[i] = st.top();
        st.push(i);
    }
    //test:
    //for(int i = 1; i <= n; i++) cout << Lnxt[i] << ' '; cout << '\n';
    //for(int i = 1; i <= n; i++) cout << Rnxt[i] << ' '; cout << '\n';
}

void solve()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build();

    int ans = INF;

    for(int i = 1; i <= n; i++)
    {
        for(int j = min(i , k); j >= 2; j--)
        {
            dp[i][j] = BIT[j-1].get_suf(Lnxt[i] + 1) + a[i];
            BIT[j].update(Rnxt[i] - 1 , dp[i][j]);

            if(j == k && Rnxt[i] == n+1)
            {
                ans = min(ans , dp[i][j]);
            }
        }

        if(Lnxt[i] == 0)
        {
            dp[i][1] = a[i];
            BIT[1].update(Rnxt[i] - 1 , dp[i][1]);
            if(k == 1 && Rnxt[i] == n+1) ans = min(ans , dp[i][1]);
        }
    }

    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt" , "r" , stdin);
    //freopen("out.txt" , "w" , stdout);
    solve();
    return 0;
}

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