Submission #1090568

#TimeUsernameProblemLanguageResultExecution timeMemory
1090568hoangnguyenhK blocks (IZhO14_blocks)C++14
53 / 100
1067 ms1764 KiB
#include<bits/stdc++.h> #define ll long long #define el '\n' #define rep(i,a,b) for (int i=a;i<=b;++i) using namespace std; ll n,k,a[100001],dp[101][100001],ma[22][100001]; ll get(ll l, ll r) { if (l>r) return 1e18; ll k=log2(r-l+1); return max(ma[k][l],ma[k][r-(1<<k)+1]); } void sol(ll g, ll l, ll r, ll ol, ll oR) { if (l>r) return; ll mid=l+r>>1; dp[g][mid]=1e18; ll pos=0; rep(i,1,mid) { ll newcost=dp[g-1][i]+get(i+1,mid); //if (g==2 && mid==6) cout<<ol<<' '<<oR<<' '<<dp[g-1][i]<<' '<<get(i+1,mid)<<' '<<i+1<<el; if (dp[g][mid]>newcost) { pos=i; dp[g][mid]=newcost; } } sol(g,l,mid-1,ol,pos); sol(g,mid+1,r,pos,oR); } void solve() { cin>>n>>k; rep(i,1,k) dp[0][i]=1e18; rep(i,1,n) { cin>>a[i]; ma[0][i]=a[i]; } for (int i=1;i<=log2(n);i++) { for (int j=1;j<=(n-(1<<i)+1);j++) ma[i][j]=max(ma[i-1][j],ma[i-1][j+(1<<(i-1))]); } rep(i,1,n) { dp[1][i]=get(1,i); } rep(i,2,k) sol(i,1,n,1,n); cout<<dp[k][n]; } int main() { solve(); return 0; }

Compilation message (stderr)

blocks.cpp: In function 'void sol(long long int, long long int, long long int, long long int, long long int)':
blocks.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     ll mid=l+r>>1;
      |            ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...