Submission #1295174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295174		k12_khoi	K blocks (IZhO14_blocks)	C++17	53 / 100	1095 ms	1824 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N=1e5+5;
const int K=105;
const ll oo=(long double)1e18+1;

int n,k;
int a[N];

namespace sub4
{
    const int oo=1e9+1;

    int ma,u,v,x;
    int dp[N],t[4*N],lazy[4*N];
    stack <int> st;

    void build(int id,int l,int r)
    {
        lazy[id]=0;
        if (l==r)
        {
            t[id]=dp[l-1];
            return;
        }
        int m=(l+r)/2;
        build(id*2,l,m);
        build(id*2+1,m+1,r);
        t[id]=min(t[id*2],t[id*2+1]);
    }

    void down(int id)
    {
        if (lazy[id])
        {
            lazy[id*2]+=lazy[id];
            lazy[id*2+1]+=lazy[id];

            t[id*2]+=lazy[id];
            t[id*2+1]+=lazy[id];

            lazy[id]=0;
        }
    }

    void update(int id,int l,int r)
    {
        if (u>r or v<l) return;
        if (u<=l and v>=r)
        {
            t[id]+=x;
            lazy[id]+=x;
            return;
        }
        down(id);
        int m=(l+r)/2;
        update(id*2,l,m);
        update(id*2+1,m+1,r);
        t[id]=min(t[id*2],t[id*2+1]);
    }

    int get(int id,int l,int r)
    {
        if (u>r or v<l) return oo;
        if (u<=l and v>=r) return t[id];
        down(id);
        int m=(l+r)/2;
        return min(get(id*2,l,m),get(id*2+1,m+1,r));
    }

    void solve()
    {
        ma=0;
        for (int i=1;i<=n;i++)
        {
            ma=max(ma,a[i]);
            dp[i]=ma;
        }

        for (int rep=2;rep<=k;rep++)
        {
            build(1,1,n);

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

            a[rep-1]=oo;
            st.push(rep-1);
            for (int i=rep;i<=n;i++)
            {
                u=st.top()+1;
                while (!st.empty() and a[st.top()]<a[i])
                {
                    v=st.top();
                    st.pop();
                    u=st.top()+1;
                    x=-a[v];

                    update(1,1,n);
                }
                v=i;
                x=a[i];
                update(1,1,n);
                st.push(i);

                u=rep;
                v=i;
                dp[i]=get(1,1,n);
            }
        }

        cout << dp[n];
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

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

    sub4::solve();
}

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