Submission #886822

#	Time	Username	Problem	Language	Result	Execution time	Memory
886822		AlphaMale06	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	1112 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

const int N = 100005;
const int K = 103;
const int inf=1e9;
int dp[N], ndp[N], pos[N], lg[N];
int sp[N][17];

int get(int l, int r){
    if(l>r)return 0;
    int rng=r-l+1;
    int lga=lg[rng];
    return max(sp[l][lga], sp[r-(1<<lga)+1][lga]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i=0; i< n; i++)cin >> a[i];
    int mx=0;
    lg[1]=0;
    for(int i=2; i<N; i++){
        lg[i]=lg[i/2]+1;
    }
    for(int i=0; i< n; i++){
        mx=max(mx, a[i]);
        dp[i]=mx;
        sp[i][0]=a[i];
    }
    for(int j=1; j<17; j++){
        for(int i=0; i+(1<<j)<=n; i++){
            sp[i][j]=max(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
        }
    }
    stack<pair<int, int>> st;
    st.push({inf, -1});
    for(int i=0; i< n; i++){
        while(!st.empty() && st.top().F<=a[i]){
            st.pop();
        }
        pos[i]=st.top().S+1;
        st.push({a[i], i});
    }
    while(!st.empty())st.pop();

    for(int j=2; j<=k; j++){
        st.push({inf, -1});
        for(int i=0; i< n; i++){
            int ps=pos[i];
            pair<int, int> lst={-2, -1};
            while(ps<=st.top().S){
                lst=st.top();
                st.pop();
                if(st.size()==0)break;
            }
            if(st.size()==0)st.push(lst);
            else if(lst.F!=-2 && st.top().F+get(st.top().S+1, i)>lst.F+get(lst.S+1, i))st.push(lst);
            ndp[i]=st.top().F+get(st.top().S+1, i);
            while(!st.empty() && st.top().F>= dp[i])st.pop();
            if(dp[i]<ndp[i])st.push({dp[i], i});
        }
        while(!st.empty())st.pop();
        for(int i=0; i< n; i++){
            dp[i]=ndp[i];
        }
    }
    cout << dp[n-1] << '\n';
}

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