Submission #1304767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304767		maithedung	K blocks (IZhO14_blocks)	C++20	0 / 100	1 ms	576 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define exit return 0
#define cap pair<int,int>
#define fi first
#define se second
#define pb push_back
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define fill(f,x) memset(f,x,sizeof(f))
#define lcm(a,b) (a/__gcd(a,b)*b)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
int n,g;
int cur[1000005];
int prevv[1000005];
int prefix[1000005];
int A[1000005];
int st[20][200005]; 
int calc(int l, int r)
{
    int lg=log2(r-l+1); 
    return max(st[lg][l],st[lg][r-(1<<lg)+1]); 
}
void solve(int l, int r, int optl, int optr)
{
    if(l>r) return;
    int mid=(l+r)>>1;
    cap best={1e18,-1};
    FOR(i,optl,min(optr,mid-1))
    {
        best=min(best,{prevv[i]+calc(i+1,mid),i});
    }
    cur[mid]=best.first;
    int opt=best.second;
    solve(l,mid-1,optl,opt);
    solve(mid+1,r,opt,optr);
}
signed main()
{
    fast;
    cin>>n>>g;
    FOR(i,1,n)
    {
        cin>>A[i];
        prefix[i]=prefix[i-1]+A[i];
    }
    FOR(i,1,n)
    {
        st[0][i]=A[i]; 
    }
    int lg=log2(n);
    FOR(i,1,lg)
    { 
        FOR(j,1,n-(1<<i)+1) st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]); 
    }
    prevv[0]=0;
    //cout<<calc(1,1)<<endl; 
    FOR(i,1,n) prevv[i]=1e18;
    FOR(i,0,n) cur[i]=1e18;
    FOR(i,1,g)
    {
        solve(1,n,0,n);
        FOR(j,0,n) prevv[j]=cur[j];
     //   FOR(j,0,n) cout<<cur[j]<<" "; 
     //   cout<<endl; 
    }
    cout<<cur[n];
    exit;
}
/*
░▒▓███████▓▒░░▒▓█▓▒░░▒▓█▓▒░▒▓███████▓▒░ ░▒▓██████▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒▒▓███▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓███████▓▒░ ░▒▓██████▓▒░░▒▓█▓▒░░▒▓█▓▒░░▒▓██████▓▒░


*/

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