Submission #1090480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090480		hoangnguyenh	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	348 KiB

blocks

#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)
{
    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 otpl, ll otpr)
{
    if (l>r) return;
    ll mid=l+r>>1;
    ll pos=0;
    dp[g][mid]=1e18;
    for (ll i=otpl;i<=min(mid-1,otpr);i++)
    {
        ll cost=dp[g-1][i]+get(i+1,mid);
        if (cost<dp[g][mid])
        {
            pos=i;
            dp[g][mid]=cost;
        }
    }
    sol(g,l,mid-1,otpl,pos);
    sol(g,mid+1,r,pos,otpr);
}
void solve()
{
    cin>>n>>k;
    rep(i,1,n)
    {
        cin>>a[i];
        dp[1][i]=max(dp[1][i-1],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,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:15:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     ll mid=l+r>>1;
      |            ~^~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47