제출 #1190712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190712		DanielPr8	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	2071 ms	125900 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

ll cur=1;
ll lc[ll(1e7)]={0}, rc[ll(1e7)]={0}, v[ll(1e7)]={0};
void sparse(ll i, ll l, ll r){
    if(l+1<r){
        if(!lc[i])lc[i]=cur++;
        if(!rc[i])rc[i]=cur++;
    }
}
void seg(ll a, ll b){
    lc[cur]=a;
    rc[cur]=b;
    v[cur++]=v[a]+v[b];
}
void seg(ll x){
    v[cur++]=x;
}
ll que(ll i, ll l, ll r, ll a, ll b){
    if(r<=a || b<=l)return 0;
    if(a<=l && r<=b)return v[i];
    sparse(i, l, r);
    return que(lc[i], l, (l+r)/2, a, b)+que(rc[i], (l+r)/2, r, a, b);
}
ll upd(ll i, ll l, ll r, ll t, ll x){
    sparse(i, l, r);
    if(l+1==r){
        seg(v[i]+x);
        return cur-1;
    }
    if(t>=(l+r)/2){
        seg(lc[i], upd(rc[i], (l+r)/2, r, t, x));
        return cur-1;
    }
    else{
        seg(upd(lc[i], l, (l+r)/2, t, x), rc[i]);
        return cur-1;
    }
}
vll hea;
ll n;
ll query(ll a, ll b, ll c, ll d){//in range (a,b) que(c,d)
    return que(hea[a], 0, n, c, d) - que(hea[b+1], 0, n, c, d);
}
vvl dp;
void calc(ll a, ll b, ll j, ll mn, ll mx){
    if(a>=b)return;
    ll i = (a+b)/2;
    ll bes = mn;
    for(ll h = mn; h < mx; ++h){
        ll p = dp[h][j-1] + query(i, n-1, h, i);
        if(p>dp[i][j]){
            bes=h;
            dp[i][j]=p;
        }
    }
    if(a+1<b){
        calc(a, (a+b)/2, j, mn, bes+1);
        calc((a+b)/2+1, b, j, bes, mx);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll a, b, d, t;
    cin >> n >> d >> t;
    vll tm(n), ls(n);
    stack<pll> w;
    w.push({-1e9, -1});
    for(ll i = 0; i < n; ++i){
        cin >> tm[i];
        w.push({tm[i], i});
        while(w.top().f+i-w.top().s>t){
            w.pop();
        }
        ls[i]=w.top().s;
    }
    hea = vll(n+1,1);
    for(ll i = n-1; i >= 0; --i){
        hea[i]=hea[i+1];
        if(ls[i]!=-1)hea[i] = upd(hea[i], 0, n, ls[i], 1);
    }
    dp = vvl(n, vll(d+1));
    for(ll j = 1; j <= d; ++j){
        calc(0, n, j, 0, n);
    }
    ll ans = n;
    for(ll i = 0; i < n; ++i){
        ans = min(ans, n-dp[i][d]);
    }
    cout << ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20