Submission #91386

#	Time	Username	Problem	Language	Result	Execution time	Memory
91386		kylych03	K blocks (IZhO14_blocks)	C++14	53 / 100	1086 ms	924 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
int dp[101][101], a[101],n,k;
int main(){
	int i,j,t;
	cin>>n>>k;
	
	
	for(i=1;i<=n; i++)
		cin>>a[i];
		
	
	for(i=1;i<=n; i++)
		dp[1][i] = max(a[i], dp[1][i-1]);
	
	for(i=2;i<=k;i++){
		
		for(j=i;j<=n;j++){
			int mx=a[j];
			dp[i][j]=dp[i-1][j-1] + a[j];
			for(t=j;t>=i; t--){
				mx=max(mx,a[t]);
				dp[i][j]=min(dp[i][j], dp[i-1][t-1] + mx);
			}
		}
	}
	cout<<dp[k][n]<<endl;
	
}

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