Submission #491077

#	Time	Username	Problem	Language	Result	Execution time	Memory
491077		tar_palantir	K blocks (IZhO14_blocks)	C++17	0 / 100	36 ms	87200 KiB

blocks

#include<bits/stdc++.h>
#define int     long long
#define task    "block"
using namespace std;
using ii=pair<int,int>;

const int mn=1e5+11;
const int mk=111;

int n,k;
int a[mn];
int dp[mn][mk];

ii st[mn];
int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin>>n>>k;
    
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    
    memset(dp,0x3f,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 j=2;j<=k;j++){
    	int cnt=0;
    	for(int i=j;i<=n;i++){
    		int mval=dp[i-1][j-1];
    		
    		while(cnt && a[st[cnt].first]<=a[i]){
    			mval=min(mval,st[cnt].second);
    			cnt--;
    		}
    		
    		dp[i][j]=min(dp[st[cnt].first][j],mval+a[i]);
    		st[++cnt]=ii(j,mval);
    	}	
    }
    
    cout<<dp[n][k];
}

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