Submission #1021671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021671		12345678	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	48 ms	11096 KiB

prison

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, d, T, dpl[nx], dpr[nx], t[nx], lst=1e9, cnt=0, res=1e9;
stack<pair<int, int>> s;

int cost(int l, int r)
{
    if (t[l]>T) return 0;
    if (t[l]+r-l<=T) return r-l+1;
    return T-t[l]+1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d>>T;
    for (int i=1; i<=n; i++) cin>>t[i];
    for (int i=1; i<=n; i++) lst=min(lst+1, t[i]), cnt+=(lst<=T), dpl[i]=cnt;
    cnt=0;
    for (int i=n; i>=1; i--)
    {
        while (!s.empty()&&t[i]-i<t[s.top().first]-s.top().first) cnt-=cost(s.top().first, s.top().second), s.pop();
        if (s.empty()) cnt+=cost(i, n), s.push({i, n});
        else cnt+=cost(i, s.top().first-1), s.push({i, s.top().first-1});
        dpr[i]=cnt;
        res=min(res, dpl[i-1]+dpr[i]);
    }
    cout<<res;
}

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