t.tie(nullptr);
int N, K;
cin >> N >> K;
for(int i = 0; i <= N; ++i){
for(int j = 0; j <= K; ++j){
dp[i][j] = INF;
}
}
for(int i = 1; i <= N; ++i) cin >> a[i];
for(int i = 0; i <= N; ++i) dp[i][0] = 0;
for(int i = 1, mx = 1; i <= N; ++i){
mx = max(mx, a[i]);
dp[i][1] = mx;
}
for(int k = 2; k <= K; ++k){
stack<int> st;
for(int i = 1; i <= N; ++i){
mn[i] = INF;
while(st.size() && a[st.top()] <= a[i]){
dp[i][k] = min(dp[i][k], dp[st.top() - 1][k - 1] + a[i]);
mn[i] = min({mn[i], dp[st.top()][k - 1], mn[st.top()]});
dp[i][k] = min(dp[i][k], mn[i] + a[i]);
st.pop();
}
if(st.size()){
dp[i][k] = min(dp[i][k], dp[st.top()][k]); // extend
dp[i][k] = min(dp[i][k], dp[st.top()][k - 1] + a[i]); // from st.top() + 1, to i
dp[i][k] = min(dp[i][k], dp[st.top() - 1][k - 1] + a[st.top()]); // (st.top() -> i)
// dp[i][k] = min(dp[i][k], mn[st.top()] + a[i]); mn[i] not equal to dp[st.top()][k - 1]
}
dp[i][k] = min(dp[i][k], dp[i - 1][k - 1] + a[i]);
st.push(i);
}
}
cout << dp[N][K] << "\n";
return 0;
}
Compilation message (stderr)
blocks.cpp:1:1: error: 't' does not name a type
1 | t.tie(nullptr);
| ^
blocks.cpp:4:5: error: 'cin' does not name a type
4 | cin >> N >> K;
| ^~~
blocks.cpp:6:5: error: expected unqualified-id before 'for'
6 | for(int i = 0; i <= N; ++i){
| ^~~
blocks.cpp:6:20: error: 'i' does not name a type
6 | for(int i = 0; i <= N; ++i){
| ^
blocks.cpp:6:28: error: expected unqualified-id before '++' token
6 | for(int i = 0; i <= N; ++i){
| ^~
blocks.cpp:12:5: error: expected unqualified-id before 'for'
12 | for(int i = 1; i <= N; ++i) cin >> a[i];
| ^~~
blocks.cpp:12:20: error: 'i' does not name a type
12 | for(int i = 1; i <= N; ++i) cin >> a[i];
| ^
blocks.cpp:12:28: error: expected unqualified-id before '++' token
12 | for(int i = 1; i <= N; ++i) cin >> a[i];
| ^~
blocks.cpp:14:5: error: expected unqualified-id before 'for'
14 | for(int i = 0; i <= N; ++i) dp[i][0] = 0;
| ^~~
blocks.cpp:14:20: error: 'i' does not name a type
14 | for(int i = 0; i <= N; ++i) dp[i][0] = 0;
| ^
blocks.cpp:14:28: error: expected unqualified-id before '++' token
14 | for(int i = 0; i <= N; ++i) dp[i][0] = 0;
| ^~
blocks.cpp:16:5: error: expected unqualified-id before 'for'
16 | for(int i = 1, mx = 1; i <= N; ++i){
| ^~~
blocks.cpp:16:28: error: 'i' does not name a type
16 | for(int i = 1, mx = 1; i <= N; ++i){
| ^
blocks.cpp:16:36: error: expected unqualified-id before '++' token
16 | for(int i = 1, mx = 1; i <= N; ++i){
| ^~
blocks.cpp:21:5: error: expected unqualified-id before 'for'
21 | for(int k = 2; k <= K; ++k){
| ^~~
blocks.cpp:21:20: error: 'k' does not name a type
21 | for(int k = 2; k <= K; ++k){
| ^
blocks.cpp:21:28: error: expected unqualified-id before '++' token
21 | for(int k = 2; k <= K; ++k){
| ^~
blocks.cpp:42:5: error: 'cout' does not name a type
42 | cout << dp[N][K] << "\n";
| ^~~~
blocks.cpp:44:5: error: expected unqualified-id before 'return'
44 | return 0;
| ^~~~~~
blocks.cpp:45:1: error: expected declaration before '}' token
45 | }
| ^