제출 #1179850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179850		altern23	K개의 묶음 (IZhO14_blocks)	C++17	0 / 100	0 ms	328 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];
			ll cur = a[i];
			for(int j = 1; j <= K; j++){
				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: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47