제출 #1021670

#제출 시각아이디문제언어결과실행 시간메모리
102167012345678The short shank; Redemption (BOI21_prison)C++17
0 / 100
1 ms604 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=505;

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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...