Submission #1026016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026016		vjudge1	K blocks (IZhO14_blocks)	C++17	53 / 100	515 ms	262144 KiB

blocks

#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back

const int lim=2e5+100;
int mod=1e9+7;

const int inf=INT_MAX;

using pii=pair<int,int>;

struct segtree{
    int n;
    vector<int>tree;
    void init(int N){
        n=N;
        tree.resize(4*N,inf);
    }
    int P,VAL;
    void update(int l,int r,int node){
        if(node==-1&&r==-1)exit(0);
        if(l==r){
            tree[node]=VAL;
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
        tree[node]=min(tree[child],tree[child|1]);
    }
    void update(int p,int val){
        P=p,VAL=val;
        update(0,n-1,1);
    }
    int L,R;
    int query(int l,int r,int node){
        if(L<=l&&r<=R){
            return tree[node];
        }
        if(r<L||R<l){
            return inf;
        }
        int mid=(l+r)>>1,child=node<<1;
        return min(query(l,mid,child),query(mid+1,r,child|1));
    }
    int query(int l,int r){
        L=l,R=r;
        return query(0,n-1,1);
    }
};


signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int dp[k+1][n];
    dp[1][0]=a[0];
    for(int i=1;i<n;i++){
        dp[1][i]=max(dp[1][i-1],a[i]);
    }
    if(k==1){
        cout<<dp[1][n-1];
        return 0;
    }
    int val[k+1][n];
    vector<int>stk;
    stk.pb(-1);
    multiset<int>goodvals[k+1];
    for(int i=0;i<=k;i++){
        goodvals[i].insert(inf);
    }
    segtree st[k];
    for(int i=0;i<k;i++){
        st[i].init(n);
    }
    for(int i=1;i<n;i++){
        st[1].update(i,dp[1][i-1]);
    }
    for(int i=0;i<n;i++){
        while(stk.back()!=-1&&a[stk.back()]<a[i]){
            for(int j=2;j<=k;j++){
                goodvals[j].erase(goodvals[j].find(val[j][stk.back()]));
            }
            stk.pop_back();
        }
        for(int j=2;j<=k;j++){
            val[j][i]=st[j-1].query(stk.back()+1,i)+a[i];
            goodvals[j].insert(val[j][i]);
        }
        for(int j=2;j<=k;j++){
            dp[j][i]=*goodvals[j].begin();
            if(j!=k&&i!=n-1)st[j].update(i+1,dp[j][i]);
        }
        stk.pb(i);
    }
    cout<<dp[k][n-1];
}

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