Submission #714416

#	Time	Username	Problem	Language	Result	Execution time	Memory
714416		Quan2003	K blocks (IZhO14_blocks)	C++17	0 / 100	180 ms	262144 KiB

blocks

#include <bits/stdc++.h>
#include <iostream> 
#include<vector>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 5e2 + 10;
const long long INF = 1e17; 
long long n,m,comp,k,s,t,q;
char g[M + 1][M + 1]; 
int block[N + 1]; 
long long dp[N + 1][M + 1];
long long a[N + 1]; 
int fa[N + 1]; 
int timer = 1;  
int main(){
      cin >> n >> k;
      for(int i = 1; i <= n; i++) cin >> a[i]; 
      memset(dp,0x3f3f3f3f,sizeof(dp));
      dp[0][1] = 0; 
      for(int i = 1; i <= n; i++) dp[i][1] = max(dp[i - 1][1], a[i]); 
      for(int i = 2; i <= k; i++){
           stack<pair<long long,int>>stk;
           for(int j = i; j <= n; j++){
               long long mn = dp[j - 1][i - 1];
               while(stk.size() && a[stk.top().second] <= a[j]){
                     mn = min(mn, stk.top().first);
                     stk.pop(); 
               }
               dp[j][i] = min(dp[stk.size() ? stk.top().second : 0][i], mn + a[j]);
               stk.push({mn,j}); 
           }
      }
      cout << dp[n][k] << endl; 
      return 0; 
}

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