# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1248117 | kokokai | K blocks (IZhO14_blocks) | C++20 | 272 ms | 166004 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+4;
ll a[N];
ll dp[N][105];
ll dp1[N][105];
ll n,K;
void solve(){
memset(dp,0x3f3f3f3f,sizeof dp);
memset(dp1,0x3f3f3f3f,sizeof dp1);
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i];
dp[0][0]=0;
for(int k=1;k<=K;k++){
vector<int> st;
dp1[k][k]=dp[k-1][k-1];
//dp1[i][k]=luu min cac dp[p+1...i][k-1] voi a[p]>a[i]
for(int i=k;i<=n;i++){
while(!st.empty() && a[st.back()] <= a[i]){
dp1[i][k]=min(dp1[i][k],dp1[st.back()][k]);
st.pop_back();
}
dp[i][k]=min(dp[i][k],dp1[i][k]+a[i]);
int i1=0;
if(!st.empty()) i1=st.back();
dp[i][k]=min(dp[i][k],dp[i1][k-1]+a[i]);
dp1[i][k]=min(dp1[i][k],dp[i][k-1]);
dp[i][k]=min(dp[i][k],dp[i1][k]);
st.push_back(i);
}
}
cout<<dp[n][K]<<'\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
if(fopen("text.inp","r")){
freopen("text.inp","r",stdin);
}
int tt=1;
//cin>>tt;
while(tt--){
solve();
}
}
Compilation message (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... |