Submission #725336

#	Time	Username	Problem	Language	Result	Execution time	Memory
725336		Rafi22	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	468 ms	251400 KiB

prison

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
 
const int N=2000007;
 
int t[N];
int R[N];
vector<int>G[N];
int h[N],g[N],ile[N];
 
void dfs(int v)
{
    h[v]=1;
    g[v]=v;
    for(auto u:G[v])
    {
        dfs(u);
        if(h[u]+1>h[v])
        {
            h[v]=h[u]+1;
            g[v]=g[u];
        }
    }
    ile[g[v]]++;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,T,ans=0;
    cin>>n>>d>>T;
    for(int i=1;i<=n;i++) cin>>t[i];
    reverse(t+1,t+n+1);
    vector<pair<int,int>>Q;
    for(int i=n;i>0;i--)
    {
        while(sz(Q)>0&&Q.back().nd>i) Q.pop_back();
        if(t[i]>T)
        {
            if(sz(Q)==0) ans++;
            else R[i]=Q.back().st-1;
        }
        else
        {
            while(sz(Q)>0&&Q.back().nd>=i-T+t[i]) Q.pop_back();
            Q.pb({i,i-T+t[i]});
        }
    }
    Q.clear();
    int it=1;
    Q.pb({1,inf});
    for(int i=1;i<=n;i++)
    {
        if(R[i]>0)
        {
            it++;
            while(Q.back().nd<R[i]) Q.pop_back();
            G[Q.back().st].pb(it);
            Q.pb({it,R[i]});
        }
    }
    dfs(1);
    vector<int>vec;
    for(int i=1;i<=it;i++) vec.pb(ile[i]);
    sort(vec.begin(),vec.end(),greater<int>());
    for(int i=0;i<min(d,sz(vec));i++) ans+=vec[i];
    cout<<n-ans+1;
 
    return 0;
}

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