# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1123432 | zNatsumi | K개의 묶음 (IZhO14_blocks) | C++20 | 207 ms | 3084 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5,
INF = 1e16;
int n, k, a[N], dp[2][N];
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
#define task "blocks"
if(fopen(task ".inp", "r")){
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i <= n; i++) dp[0][i] = dp[1][i] = INF;
dp[0][0] = 0;
for(int j = 1; j <= k; j++){
stack<int> st;
for(int i = 1; i <= n; i++){
dp[1][i] = dp[0][i - 1] + a[i];
while(st.size() && a[st.top()] <= a[i]){
if(dp[0][st.top()] != INF) dp[1][i] = min(dp[1][i], dp[0][st.top()] + a[i]);
if(dp[1][st.top()] != INF) dp[1][i] = min(dp[1][i], dp[1][st.top()] - a[st.top()] + a[i]);
st.pop();
}
if(st.size()){
if(dp[1][st.top()] != INF) dp[1][i] = min(dp[1][i], dp[1][st.top()]);
if(dp[0][st.top()] != INF) dp[1][i] = min(dp[1][i], dp[0][st.top()] + a[i]);
if(dp[0][st.top() - 1] != INF) dp[1][i] = min(dp[1][i], dp[0][st.top() - 1] + a[st.top()]);
}
else if(j == 1) dp[1][i] = a[i];
st.push(i);
}
for(int i = 0; i <= n; i++){
dp[0][i] = dp[1][i];
dp[1][i] = INF;
}
}
cout << dp[0][n];
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |