이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define newl '\n'
const int N = 1e5 + 10;
const int K = 1e2 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
long long a[N + 1],n,k;
long long f[K + 1][N + 1];
void readData(){
std::cin >> n >> k;
for(int i = 1;i <= n;++i){
std::cin >> a[i];
}
}
long long solve(){
for(int i = 0;i <= k;++i){
for(int j = 0;j <= n;++j){
f[i][j] = INF;
}
}
f[0][0] = 0;
for(int i = 1;i <= k;++i){
std::stack<std::pair<int,long long>> st;
for(int j = i;j <= n;++j){
long long min_f = f[i - 1][j - 1];
while(!st.empty() && a[j] >= a[st.top().first]){
min_f = std::min(min_f,st.top().second);
st.pop();
}
f[i][j] = std::min(f[i][st.empty() ? 0 : st.top().first],min_f + a[j]);
st.push({i,min_f});
}
}
return f[k][n];
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
readData();
std::cout << solve();
return 0;
}
# | 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... |