Submission #410839

#	Time	Username	Problem	Language	Result	Execution time	Memory
410839		MasterTaster	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	332 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]);
    for (int i=2; i<=n; i++)
    {
        //cout<<i<<endl;
        for (int j=1; j<=min(k, i); j++)
        {
            //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-2)+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=i+1; j<=k; j++) dp[i][j]=MAXX;
 
      
        for (int j=1; j<=k; j++) { /*cout<<"apdejtujem "<<j<<" "<<i-1<<endl;*/ upd(j, 1, 0, n-1, i-1, dp[i][j]); }
    }
 
    cout<<dp[n][k];
 
}

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