This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;
const int maxn = 100004;
vector<int> v;
int dp[102][maxn];
int f[102][maxn];
int tree[102][4*maxn];
int fst_mx[maxn];
void build(int num,int v,int l,int r){
if(l == r && num == 1){
tree[num][v] = dp[num][l];
return;
}
if(l == r){
tree[num][v] = 1e9;
return;
}
int m = (l+r)/2;
build(num,v*2,l,m);
build(num,v*2+1,m+1,r);
tree[num][v] = min(tree[num][v*2],tree[num][v*2+1]);
}
int get_min(int num,int v,int l,int r,int le,int re){
if(l>=le && r <=re)return tree[num][v];
if(l > re || r < le)return 1e9;
int m = (l+r)/2;
int a = get_min(num,v*2,l,m,le,re);
int b = get_min(num,v*2+1,m+1,r,le,re);
return min(a,b);
}
void set_pos(int num,int v,int l,int r,int need){
if(l == r){
tree[num][v] = dp[num][l];
return;
}
int m = (l+r)/2;
if(need<=m)set_pos(num,v*2,l,m,need);
else set_pos(num,v*2+1,m+1,r,need);
tree[num][v] = min(tree[num][v*2],tree[num][v*2+1]);
}
int n,k;
void brute(){
for(int cnt(2);cnt<=k;cnt++){
for(int i(cnt);i<=n;i++){
f[cnt][i] = 1e9;
int now = v[i];
for(int to(i-1);to>=cnt-1;to--){
//if(cnt == 3)cout << i << ' ' << to << ' ' << f[cnt-1][to] << endl;
f[cnt][i] = min(f[cnt][i],now+f[cnt-1][to]);
}
}
}
cout << f[k][n] << endl;
}
main(){
ios_base::sync_with_stdio(0);
cin >> n >> k;
v.push_back(0);
int now = 0;
dp[1][0] = f[1][0] = 1e9;
for(int i(1); i <= n;i++){
int x; cin >> x;
now = max(now,x);
f[1][i] = dp[1][i] = now;
v.push_back(x);
fst_mx[i] = -1;
}
/*stack<int> s;
for(int i(0); i < n;i++){
while(s.size() && (v[s.top()] < v[i]))s.pop();
if(s.size())fst_mx[i] = s.top();
s.push(i);
}
for(int i(1);i<=k;i++)build(i,1,0,n);
//cout << get_min(2,1,0,n,0,3) << endl;
for(int cnt(2);cnt<=k;cnt++){
for(int i(cnt);i<=n;i++){
int now = 1e9;
if(dp[cnt-1][i-1]!=1e9){
now = dp[cnt-1][i-1]+v[i];
}
int nxt = fst_mx[i];
int to = 0;
//cout << now << endl;
if(nxt!=-1){
now = min(now,dp[cnt][nxt]);
to = nxt+1;
}
//cout << now << endl;
if(to!=i)now = min(now,v[i]+get_min(cnt-1,1,0,n,to,i-1));
//cout << i << ' ' << v[i] << ' ' << to << ' ' << i-1 << ' ' << get_min(cnt-1,1,0,n,to,i-1) << endl;
dp[cnt][i] = now;
//cout << cnt << ' ' << i << ' ' << now << ' ' << to << ' ' << i << endl;
set_pos(cnt,1,0,n,i);
}
}
cout << dp[k][n];*/
brute();
return 0;
}
/*
5 3
1 1 1 1 1
*/
Compilation message (stderr)
blocks.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# | 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... |