Submission #1198468

#TimeUsernameProblemLanguageResultExecution timeMemory
1198468steve_cspK blocks (IZhO14_blocks)C++17
0 / 100
3 ms3656 KiB
#include <bits/stdc++.h> using namespace std; //#define ll long long//#define fi first//#define se second #define ll long long #define memaybeo main #define en "\n"; #define hackspeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define dafug return 0; const int mmb = 1e5+2; int n,k,a[mmb],lef[mmb]; ll seg[4*mmb],dp[mmb][102]; void update(int x,int l,int r,int i,int vl) { if (l == r) { seg[x] = vl; return; } int m = (l+r)/2; if (i <= m) update(2*x,l,m,i,vl); else update(2*x+1,m+1,r,i,vl); seg[x] = min(seg[2*x],seg[2*x+1]); } ll MIN(int x,int l,int r,int i,int j) { if (j < l || i > r) return 1e18; if (i <= l && j >= r) return seg[x]; int m = (l+r)/2; return min(MIN(2*x,l,m,i,j) , MIN(2*x+1,m+1,r,i,j)); } void dopdop() { cin >> n >> k;fill(dp[0],dp[0]+k+1,(ll)1e18); for(int i=1;i<=n;++i) cin >> a[i] , fill(dp[i],dp[i]+k+1,(ll)1e18); dp[1][1] = a[1]; for(int i=2;i<=n;++i) dp[i][1] = max((ll)a[i],dp[i-1][1]); /////////////// stack<int> st; for(int i=n;i>0;--i) { while(!st.empty() && a[i] > a[st.top()]) lef[st.top()] = i , st.pop(); st.push(i); } while(!st.empty()) lef[st.top()] = 0 , st.pop(); //cout << en;for(int i=1;i<=n;++i) cout << lef[i] << ' ';cout << en; ////////////// for(int j=2;j<=k;++j) { fill(seg,seg+4*mmb,(ll)1e18); for(int i=1;i<j;++i) update(1,1,n,i,dp[i][j-1]);// , cout << dp[i][j-1] << en; //cout << MIN(1,1,n,1,1) << en; for(int i=j;i<=n;++i) { int lim = max(lef[i],j-1); dp[i][j] = min(MIN(1,1,n,lim,i-1) + (ll)a[i] , dp[lef[i]][k]); //cout << MIN(1,1,n,lim,i-1) << ' ' << lim << ' ' << i-1 << en; update(1,1,n,i,dp[i][j-1]); } } /*cout << en; for(int i=1;i<=n;++i) { for(int j=1;j<=k;++j) cout << dp[i][j] << ' ';cout << en; }*/ cout << dp[n][k]; } signed memaybeo() { hackspeed //skibidi(); dopdop(); //yesyes(); dafug }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...