Submission #847307

#	Time	Username	Problem	Language	Result	Execution time	Memory
847307		Ahmed57	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	148 ms	18512 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,k,T;cin>>n>>k>>T;
    int arr[n];
    for(int i = 0;i<n;i++)cin>>arr[i];
    int la = 0;
    int pref[n] = {0};
    for(int i = 0;i<n;i++){
        if(i==0){
            la = arr[i];
            pref[i] = (arr[i]<=T);
        }else{
            if(la+1<=arr[i]){
                la++;
                pref[i] = (la<=T);
            }else{
                la = arr[i];
                pref[i] = (arr[i]<=T);
            }
            pref[i] += pref[i-1];
        }
    }
    stack<pair<pair<int,int>,int>> suf;int suff[n+1] = {0};
    long long an = 0;
    for(int i = n-1;i>=0;i--){
        long long val = arr[i]-i;
        an+=(arr[i]<=T);
        int st  = i+1;
        while(!suf.empty()&&suf.top().first.first>=val){
            int xd = suf.top().first.second;
            int len1 = 0;
            if(xd<=T){
                len1 = min(suf.top().second,(T-xd+1));
            }
            int len2 = 0;
            xd = arr[i];
            if(xd+(st-i)<=T){
                len2 = min(suf.top().second,(T-(xd+(st-i))+1));
            }
            an+=max(0ll,len2-len1);
            st+=suf.top().second;
            suf.pop();
        }
        suf.push({{val,arr[i]},st-i});
        suff[i] = an;
    }
    int all = 1e18;
    for(int i = 0;i<n;i++){
        all = min(all,pref[i]+suff[i+1]);
    }
    cout<<all<<endl;
}

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