Submission #1101498

#TimeUsernameProblemLanguageResultExecution timeMemory
1101498nguyhoangphuK blocks (IZhO14_blocks)C++17
100 / 100
385 ms49488 KiB
#include <bits/stdc++.h> using namespace std; #define mask(i) (1<<i) const int N=1e5; int n,k; int a[N+2],mx[N+2][21],dp[N+2][102],L[N+2]; int get(int l,int r) { int k=__lg(r-l+1); return min(mx[l][k],mx[r-mask(k)+1][k]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>k; for (int i=1;i<=n;i++) cin>>a[i]; stack<int> st; a[0]=1e6+1; st.push(0); for (int i=1;i<=n;i++) { while (a[st.top()]<=a[i]) st.pop(); L[i]=st.top(); st.push(i); } memset(dp,0x3f,sizeof dp); dp[0][0]=0; for (int j=1;j<=k;j++) { for (int i=0;i<=n;i++) mx[i][0]=dp[i][j-1]; for (int j=1;mask(j)<=n+1;j++) for (int i=0;i+mask(j)-1<=n;i++) mx[i][j]=min(mx[i][j-1],mx[i+mask(j-1)][j-1]); for (int i=1;i<=n;i++) { dp[i][j]=min(dp[i][j],get(L[i],i-1)+a[i]); dp[i][j]=min(dp[i][j],dp[L[i]][j]); } } cout<<dp[n][k]; }

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:34:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |     mx[i][j]=min(mx[i][j-1],mx[i+mask(j-1)][j-1]);
      |                                       ~^~
blocks.cpp:3:21: note: in definition of macro 'mask'
    3 | #define mask(i) (1<<i)
      |                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...