#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
using namespace std;
int n,k;
int a[100001];
int st[400001];
int dp[100001][101];
void upd(int id,int l,int r,int i,int v) {
if (l>i||r<i) return;
if (l==r) {
st[id]=v;
return;
}
int mid=(l+r)>>1;
upd(id<<1,l,mid,i,v);
upd(id<<1|1,mid+1,r,i,v);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v) {
if (l>v||r<u) return 0;
if (l>=u&&r<=v) return st[id];
int mid=(l+r)>>1;
return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
int F(int x,int y) {
if (dp[x][y]) return dp[x][y];
if (y==k-1) return dp[x][y]=get(1,1,n,x,n);
dp[x][y]=1e9;
for (int i=x;i<=n+1-(k-y);++i) dp[x][y]=min(dp[x][y],get(1,1,n,x,i)+F(i+1,y+1));
return dp[x][y];
}
int main() {
cin.tie(0)->ios_base::sync_with_stdio(0);
cin>>n>>k;
for (int i=1;i<=n;++i) {
cin>>a[i];
upd(1,1,n,i,a[i]);
}
cout<<F(1,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... |