Submission #1029156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029156		happy_node	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	1 ms	348 KiB

prison

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e6+5;

int N,D,T;

int A[MX],B[MX];
bool C[MX];

int main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

        cin>>N>>D>>T;

        for(int i=1;i<=N;i++) {
                cin>>A[i];
                B[i]=A[i]-i;
        }

        for(int d=0;d<D;d++) {
                vector<int> stk;

                vector<int> cnt(N+1);
                for(int i=1;i<=N;i++) {
                        while(stk.size() && B[stk.back()]>=B[i]) stk.pop_back();
                        if(A[i]<=T) {
                                stk.push_back(i);
                        } else {
                                if(stk.size() && A[stk.back()]+i-stk.back()<=T) {
                                        cnt[stk.back()]+=1;
                                        cnt[i]-=1;
                                }
                        }

                        if(C[i]) stk.clear();
                }

                int arg=0;
                for(int i=1;i<=N;i++) {
                        cnt[i]+=cnt[i-1];
                        if(cnt[i]>cnt[arg]) arg=i;
                }

                C[arg]=true;
        }

        vector<int> stk;

        int ans=0;
        for(int i=1;i<=N;i++) {
                while(stk.size() && B[stk.back()]>=B[i]) stk.pop_back();

                if(A[i]<=T) {
                        ans++;
                } else {
                        if(stk.size() && A[stk.back()]+i-stk.back()<=T) ans++;
                }

                if(C[i]) stk.clear();
        }

        cout<<ans<<'\n';
}

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