Submission #171878

#TimeUsernameProblemLanguageResultExecution timeMemory
171878SwanK blocks (IZhO14_blocks)C++14
0 / 100
62 ms4984 KiB
#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 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]); } main(){ ios_base::sync_with_stdio(0); int n,k; cin >> n >> k; v.push_back(0); int now = 0; dp[1][0] = 1e9; for(int i(1); i <= n;i++){ int x; cin >> x; now = max(now,x); 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]; return 0; } /* 5 4 1 2 3 4 5 */

Compilation message (stderr)

blocks.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...