Submission #1156565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156565		sodbayr	K blocks (IZhO14_blocks)	C++20	100 / 100	80 ms	4168 KiB

blocks

#include<bits/stdc++.h>
#define int long long
#define ss second
#define ff first
#define pb push_back
const int mxn=100005;
using namespace std;
int a[mxn],l[mxn],mn[mxn];
int dp[mxn][2];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,s;
    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,100,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%2]=dp[0][0];
		}
        for(int i=k; i<=n; i++) {
            mn[i]=dp[i-1][(k-1)%2];
            for(int j=i-1; j>l[i]; j=l[j])
            {
            	mn[i]=min(mn[i],mn[j]);
			}
            dp[i][k%2]=min(dp[l[i]][k%2],mn[i]+a[i]);
        }
    }
    cout<<dp[n][s%2];
}

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