Submission #1028097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028097		12345678	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	312 ms	241372 KiB

prison

#include <bits/stdc++.h>

using namespace std;

const int nx=2e6+5;

int n, k, T, t[nx], l[nx], res, dp[nx];
vector<int> rt, d[nx];
priority_queue<int> pq;

void dfs(int u)
{
    pair<int, int> mx;
    for (auto v:d[u]) dfs(v), mx=max(mx, {dp[v], v});
    for (auto v:d[u]) if (v!=mx.second) pq.push(dp[v]);
    if (mx.second) dp[u]=dp[mx.second]+1;
    else dp[u]=1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>T;
    res=n;
    for (int i=1; i<=n; i++) cin>>t[i];
    stack<int> s;
    for (int i=1; i<=n; i++)
    {
        if (t[i]<=T)
        {
            while (!s.empty()&&t[s.top()]+i-s.top()>=t[i]) s.pop();
            s.push(i);
        }
        else
        {
            while (!s.empty()&&t[s.top()]+i-s.top()>T) s.pop();
            if (!s.empty()) l[i]=s.top();
            else res--;
        }
    }
    //for (int i=1; i<=n; i++) cout<<"l "<<i<<' '<<l[i]<<'\n';
    while (!s.empty()) s.pop();
    for (int i=1; i<=n; i++)
    {
        if (!l[i]) continue;
        while (!s.empty()&&l[i]<=l[s.top()]) d[i].push_back(s.top()), s.pop();
        s.push(i);
    }
    while (!s.empty()) dfs(s.top()), pq.push(dp[s.top()]), s.pop();
    while (!pq.empty()&&k--) res-=pq.top(), pq.pop();
    cout<<res;
}

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