Submission #1127663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127663		thanhphu	K blocks (IZhO14_blocks)	C++20	100 / 100	86 ms	4320 KiB

blocks

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int INF = 1e18;
int n, s;
int a[100001], l[100001], mn[100001];
int dp[100001][2];
signed main(){
    IOS;
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        for (l[i] = i - 1; l[i] > 0 && a[l[i]] <= a[i];)
                l[i] = l[l[i]];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) dp[i][1] = max(dp[i - 1][1], a[i]);
    for(int k=2;k<=s;k++)
    {
        mn[k-1]=dp[0][0];
        for(int i=1;i<=n;i++)
            dp[i][k&1]=dp[0][0];
        for(int i=k;i<=n;i++)
        {
            mn[i]=dp[i-1][(k-1)&1];
            for(int j=i-1;j > l[i];j=l[j])
                    mn[i]=min(mn[i],mn[j]);
            dp[i][k&1]=min(dp[l[i]][k&1],mn[i]+a[i]);
        }
    }
    cout<<dp[n][s&1];
}

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