Submission #1180181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180181		altern23	K blocks (IZhO14_blocks)	C++17	53 / 100	1095 ms	3144 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 4e18;
const int MOD = 998244353;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;		
	for(;tc--;){
		ll N, K; cin >> N >> K;
		vector<vector<ll>> dp(N + 5, vector<ll>(K + 5, INF));
		vector<ll> a(N + 5);
		dp[0][0] = 0;
		for(int i = 1; i <= N; i++){
			cin >> a[i];
			for(int j = 1; j <= K; j++){
				ll cur = a[i];
				for(int k = i; k >= 1; --k){
					cur = max(cur, a[k]);
					dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + cur);
				}
			}
		}
		cout << dp[N][K] << "\n";
	}
}

/*
1 2 3 4 5 6 7
*/

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