Submission #89865

#	Time	Username	Problem	Language	Result	Execution time	Memory
89865		Bodo171	K blocks (IZhO14_blocks)	C++14	100 / 100	184 ms	16120 KiB

blocks

#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
const int nmax=100005;
long long v[nmax],dp[2][nmax],mn[nmax],act[nmax];
int st[nmax];
int n,k,i,j,use,u;
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(i=0;i<=n;i++)
        dp[0][i]=1LL*1e15,dp[1][i]=1LL*1e15;
    mn[0]=1LL*1e15;dp[0][0]=0;
    for(int cnt=1;cnt<=k;cnt++)
    {
        use=1-use;u=0;
        for(i=1;i<=n;i++)
        {
            act[i]=1LL*1e15;
            while(u>0&&v[i]>=v[st[u]])
            {
                act[i]=min(act[st[u]],act[i]);
                u--;
            }
            st[++u]=i;act[i]=min(act[i],dp[1-use][st[u-1]]);
            mn[u]=min(mn[u-1],1LL*act[i]+v[i]);
            dp[use][i]=1LL*mn[u];
            act[i]=min(act[i],dp[1-use][i]);
        }
        for(i=0;i<=n;i++)
            dp[1-use][i]=1LL*1e15;
    }
    cout<<dp[use][n];
    return 0;
}

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