제출 #887116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887116		AlphaMale06	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	330 ms	10024 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(st.size() && ps<st.top().S){
                lst=st.top();
                st.pop();
            }
            if(st.size()==0 || (lst.F!=-2 && st.top().F+get(st.top().S+1, i)>lst.F+get(lst.S+1, i)))st.push(lst);
            while(st.size()>1){
                pair<int, int> p1=st.top();
                st.pop();
                pair<int, int> p2=st.top();
                if(p1.F+get(p1.S+1, i)<p2.F+get(p2.S+1, i)){
                    st.push(p1);
                    break;
                }
            }
            ndp[i]=st.top().F+get(st.top().S+1, i);
            while(st.size() && 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: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47