Submission #866956

#	Time	Username	Problem	Language	Result	Execution time	Memory
866956		HossamHero7	The short shank; Redemption (BOI21_prison)	C++14	10 / 100	45 ms	8916 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void solve(){
    int n,d,t;
    cin>>n>>d>>t;
    vector<int> v(n);
    for(auto &i:v) cin>>i;
    vector<int> suffix(n+1);
    vector<int> starts;
    for(int i=n-1;i>=0;i--){
        suffix[i] = suffix[i+1];
        int sz = 1;
        while(starts.size()){
            int a = starts.back();
            if(v[a] >= v[i]+(a-i)) {
                starts.pop_back();
                int sz2 = (starts.size() ? starts.back() - a : n - a);
                suffix[i] -= min((max(0,t-v[a]+1)),sz2);
                sz += sz2;
            }
            else break;
        }
        starts.push_back(i);
        suffix[i] += min((max(0,t-v[i]+1)),sz);
    }
    int lst = v[0];
    int prefix = (lst <= t);
    int ans = prefix + suffix[1];
    for(int j=1;j<n-1;j++) {
        if(v[j] > lst) lst ++;
        else lst = v[j];
        prefix += (lst <= t);
        ans = min(ans,prefix+suffix[j+1]);
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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