제출 #991051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991051		hgmhc	K blocks (IZhO14_blocks)	C++17	0 / 100	10 ms	41676 KiB

blocks

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int32_t((x).size())
#define Mup(x,y) (x = max(x,y))
#define mup(x,y) (x = min(x,y))
#define fi first
#define se second
#define pb push_back
#define dbg(...) fprintf(stderr,__VA_ARGS__)
// #define int long long

template <class T, const int N>
struct PURQ {
    int n; T t[2*N]; T (*op)(T,T);
    void set(int _n, T e, T f(T,T)) { n=_n, fill(t,t+2*n,e), op=f; }
    void update(int k, T v) {
        assert(0 <= k and k < n);
        k += n;
        for (t[k] = v; (k /= 2) >= 1; t[k] = op(t[2*k],t[2*k+1]));
    }
    T query(int a, int b) {
        assert(0 <= a and a-1 <= b and b < n);
        T l = t[0], r = t[0];
        for (a += n, b += n; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) l = op(l,t[a]);
            if (~b&1) r = op(t[b],r);
        }
        return op(l,r);
    }
};

const ll N = 1e5+3, K = 103;
const int INF = 1e9;
int n, A[N], k;
PURQ<int,N> rmq;
int dp[N][K];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    
    rmq.set(n+1, -INF, [](int x, int y){ return max(x,y); });
    rep(i,1,n) cin >> A[i], rmq.update(i,A[i]);
    
    fill(dp[0],dp[N],INF);
    dp[0][0] = 0;
    
    rep(i,1,n) {
        rep(j,1,min(k,i)) {
            int a=j,b=i,m;
            //    단조증가            단조감소
            // dp[m-1][k-1] + rmq.query(m,i)
            
            // rmq.query(m,i)=c인 애들 중 가장 인덱스가 작은 위치로 m 옮기기
            
            auto f = [i,j](int x) -> int {
                return dp[x-1][j-1] + rmq.query(x, i);
            };
            
            auto lb = [i](int x) -> int {
                x = rmq.query(x,i);
                int a=1, b=i, m;
                while (a<=b) {
                    m=(a+b)/2;
                    if (rmq.query(m,i)>x) a=m+1;
                    else b=m-1;
                }
                assert(rmq.query(a,i) == x);
                
                if (a>1)
                    assert(rmq.query(a-1,i) > x);
                return a;
            };
            
            while (a<=b) {
                m=(a+b)/2;
                if (f(lb(lb(m)-1)) > f(lb(m))) a=m+1;
                else b=m-1;
            }
            mup(dp[i][j], f(max(j,lb(a))));
        }
    }
    cout << dp[n][k];
}

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