Submission #411200

#	Time	Username	Problem	Language	Result	Execution time	Memory
411200		MasterTaster	K blocks (IZhO14_blocks)	C++14	53 / 100	1103 ms	118984 KiB

blocks

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXX 100000000010LL
#define MAXN 100010
#define MAXK 110

using namespace std;

ll seg[MAXK][4*MAXN], dp[MAXN][MAXK], a[MAXN];
int n, k, lv[MAXN];

ll query(int i, int node, int l, int r, int levo, int desno)
{
    if (levo>r || desno<l) return MAXX;
    if (levo<=l && desno>=r) return seg[i][node];

    int mid=l+(r-l)/2;
    return min(query(i, 2*node, l, mid, levo, desno),
               query(i, 2*node+1, mid+1, r, levo, desno));
}
void upd(int i, int node, int l, int r, int pos, ll val)
{
    if (pos>r || pos<l) return;
    if (l==r) { seg[i][node]=val; return; }

    int mid=l+(r-l)/2;
    upd(i, 2*node, l, mid, pos, val);
    upd(i, 2*node+1, mid+1, r, pos, val);
    seg[i][node]=min(seg[i][2*node], seg[i][2*node+1]);
}

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

    cin>>n>>k;

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

    stack<pii> st;
    st.push({1000010, 0});
    for (int i=1; i<=n; i++)
    {
        while (st.top().xx<a[i]) st.pop();
        lv[i]=st.top().yy;
        //cout<<lv[i]<<" ";

        st.push({a[i], i});
    }
    //cout<<endl;

    for (int i=0; i<=n; i++) for (int j=0; j<=k; j++) { dp[i][j]=MAXX; upd(j, 1, 0, n-1, max(0, i-1), MAXX); }

    dp[1][1]=a[1]; upd(1, 1, 0, n-1, 0, dp[1][1]);
    //cout<<query(1, 1, 0, n-1, 0, 0)<<endl;
    //cout<<query(0, 1, 0, n-1, 0, 0)<<endl;
    for (int i=2; i<=n; i++)
    {
        //cout<<i<<endl;
        for (int j=1; j<=min(k, i); j++)
        {
            if (j==1 && lv[i]==0) { dp[i][j]=a[i]; /*cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;*/ continue; }
            //cout<<"trazim "<<j-1<<" "<<lv[i]-1<<" "<<i-2<<endl;
            dp[i][j]=query(j-1, 1, 0, n-1, max(0, lv[i]-1), i-1)+a[i];
            //dp[i][j]=min(dp[i][j], query(j, 1, 0, n-1, lv[i], i-1)+a[i]);
            //cout<<dp[i][j]<<" ";
            dp[i][j]=min(dp[i][j], dp[lv[i]][j]);
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }

        for (int j=1; j<=min(k, i); j++) { /*cout<<"apdejtujem "<<j<<" "<<i-1<<endl;*/ upd(j, 1, 0, n-1, i-1, dp[i][j]); }
    }

    cout<<dp[n][k];

}

/*
5 3
1 | 4 2 5 | 3
*/

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