Submission #499163

#	Time	Username	Problem	Language	Result	Execution time	Memory
499163		reni	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	332 KiB

blocks

#include <bits/stdc++.h>
#define endl '\n'
#include<stack>
using namespace std;
stack<long long>st;
long long a[10000000], pr[10000000], dp[1000000][100];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long n,i,j,k;
    cin>>n>>k;
    for(i=1; i<=n; i++)
    {
      cin>>a[i];

      while(!st.empty() && a[st.top()]<=a[i])st.pop();

      if(!st.empty())pr[i]=st.top();

      st.push(i);
    }
    for(j=1;j<=n;j++)dp[j][1]=max(a[j], dp[j-1][1]);


    for(i=1;i<=n;i++)
    {
        for(j=2;j<=k;j++)
        {
            int p=0;
            if(pr[i]==0){pr[i]=j-1;p=1;}

            if(dp[pr[i]][j]!=(long long)(0) && !p) dp[i][j]=min(dp[pr[i]][j-1]+a[i], dp[pr[i]][j]);
            else dp[i][j]=dp[pr[i]][j-1]+a[i];

           if(p)pr[i]=0;
        }
    }
    cout<<dp[n][k]<<endl;

}

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