Submission #1025861

#TimeUsernameProblemLanguageResultExecution timeMemory
1025861ttamxThe short shank; Redemption (BOI21_prison)C++17
0 / 100
62 ms24032 KiB
#include<bits/stdc++.h> using namespace std; const int INF=INT_MAX/2; int main(){ cin.tie(nullptr)->sync_with_stdio(false); int n,d,t; cin >> n >> d >> t; vector<int> a(n); for(auto &x:a)cin >> x; vector<int> pre(n,-1); stack<pair<int,int>> s; s.emplace(-INF,-1); for(int i=0;i<n;i++){ int x=min(a[i],t)-i; while(s.top().first>x)s.pop(); pre[i]=a[i]>t?s.top().second:-1; s.emplace(a[i]-i,i); } vector<pair<int,int>> range; for(int i=0;i<n;i++)if(pre[i]!=-1)range.emplace_back(pre[i],i-1); int m=range.size(); vector<vector<int>> g(m); vector<int> par(m,-1); stack<pair<int,int>> st; for(int i=0;i<m;i++){ int x=range[i].first; while(!st.empty()&&st.top().first>=x){ int j=st.top().second; st.pop(); g[i].emplace_back(j); par[j]=i; } st.emplace(x,i); } vector<int> b; function<int(int)> dfs=[&](int u){ vector<int> dep; for(auto v:g[u])dep.emplace_back(dfs(v)); if(dep.empty())return 1; sort(dep.begin(),dep.end()); b.insert(b.end(),dep.begin(),dep.end()-1); return dep.back()+1; }; for(int i=0;i<m;i++)if(par[i]==-1)b.emplace_back(dfs(i)); sort(b.rbegin(),b.rend()); cout << n-accumulate(b.begin(),b.begin()+min(d,(int)b.size()),0); }
#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...