Submission #524097

#	Time	Username	Problem	Language	Result	Execution time	Memory
524097		inluminas	K blocks (IZhO14_blocks)	C++17	100 / 100	348 ms	81408 KiB

blocks

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=1e5+10;
ll dp[lmt][101];

int main(){
  fastio;

  for(int i=0;i<lmt;i++){
    for(int j=2;j<101;j++) dp[i][j]=1e12;
  }

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

  for(int i=1;i<=n;i++){
    dp[i][1]=max(dp[i-1][1],a[i]); 
  }

  for(int j=2;j<=k;j++){
    stack<pair<int,ll>>s;
    for(int i=1;i<=n;i++){
      ll mn=1e12;
      while(!s.empty() && a[s.top().first]<=a[i]){
        mn=min(mn,s.top().second);
        s.pop();
      }

      dp[i][j]=min(dp[i][j],mn+a[i]);
      
      if(!s.empty()){
        dp[i][j]=min(dp[i][j],dp[s.top().first][j-1]+a[i]);
        dp[i][j]=min(dp[i][j],dp[s.top().first][j]);
      }

      mn=min(mn,dp[i][j-1]);

      s.push({i,mn});

    }
  }

  cout<<dp[n][k]<<endl;
  return 0;
}

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