Submission #1127640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127640		hd4866596	K blocks (IZhO14_blocks)	C++20	100 / 100	168 ms	165344 KiB

blocks

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e9+7;
int n,k,a[100005];
ll dp[100005][105];
ll f[100005][105];
int main(){
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    memset(dp,inf,sizeof(dp));
    memset(f,inf,sizeof(f));
    a[0]=inf;
    stack<int> q;
    q.push(0);
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        while(!q.empty()&&a[q.top()]<a[i]){
            for(int j=1;j<=k;j++){
                f[i][j]=min(f[q.top()][j],f[i][j]);
                dp[i][j]=min(f[q.top()][j-1]+a[i],dp[i][j]);
            }
            q.pop();
        }
        int x=q.empty()?0:q.top();
        for(int j=1;j<=k;j++){
            dp[i][j]=min({dp[i][j],dp[x][j],dp[x][j-1]+a[i]});
            f[i][j]=min(f[i][j],dp[i][j]);
        }
        q.push(i);
    }
    cout << dp[n][k];
}

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