제출 #1287620

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

prison

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
    ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
    return c;
}
vi v,v2;
ll n,a,t,d;
vi g[2000007];
bool cz[2000007];
ll il[2000007];
ll dp[2000007];
ll dfs(ll v){
    dp[v]=1;
    for(ll i:g[v]){
        dp[v]=max(dp[v],dfs(i)+1);
    }
    return dp[v];
}
void dfs2(ll v,bool b){
    pii c={1,-1};
    for(ll i : g[v])c=max(c,{dp[i]+1,i});
    if(!b)il[c.ff]++;
    for(ll i : g[v])dfs2(i,(i==c.ss));
}
void solve(){
    cin>>n>>d>>t;
    for(ll i=0;i<n;i++){
        cin>>a;
        v.pb(i+t-a);
    }
    ll mx=-1;
    a=0;
    for(ll i=0;i<n;i++){
        mx=max(mx,v[i]);
        v2.pb(mx);
        if(mx>=i)cz[i]=1;
        a+=cz[i];
    }
    stack<pii>s;
    for(ll i=0;i<n;i++){
        if(!cz[i])continue;
        while(s.size() && s.top().ff<max(v2[i],i-1)){
            if(v[i]<i && v[s.top().ss]<s.top().ss)g[i].pb(s.top().ss);
            else if(v[s.top().ss]<s.top().ss)
            g[n].pb(s.top().ss);
            s.pop();
        }
        s.push({v[i],i});
    }
    while(s.size()){
        if(v[s.top().ss]<s.top().ss)
        g[n].pb(s.top().ss);
        s.pop();
    }
    dfs(n);
    dfs2(n,0);
    for(ll i=2000006;i>=0;i--){
        while(d && il[i]){
            d--;
            a-=i;
            il[i]--;
        }
    }
    cout<<a+1;
}
int main(){
    fct[0]=1;
    for(ll i=1;i<1000007;i++)fct[i]=(fct[i-1]*i)%MOD;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}

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