| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1123186 | razivo | The short shank; Redemption (BOI21_prison) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
using namespace std;
vector<long long> v(2e6);
vector<bool> fil(2e6);
pair<pair<long long,long long>,long long> opt(long long i, long long j) {
long long best = 0;
long long bestpos = j-1;
long long last = j-1;
vector<long long> q;
long long val = 0;
for (long long k = i; k < j; ++k) {
if(v[k]==-1) {
if(val>0) {
val--;
fil[k]=true;
}else {
fil[k]=false;
}
}else {
fil[k]=true;
val = max(val,v[k]);
}
}
long long cnt = 0;
for (long long k = j-1; k >=i; --k) {
if(v[k]==-1) {
if(!fil[k]) cnt++;
q.push_back(k);
continue;
}
long long p = k+v[k];
long long v = 0;
if(q.size()-cnt>best) {
best=q.size()-cnt;
bestpos=k;
}
if(!fil[k]) cnt++;
while(!q.empty() && q.back()<p) {
q.pop_back();
}
}
return {{cnt,best},bestpos};
}
long long main() {
long long n,d,t; cin>>n>>d>>t;
for (long long i = 0; i < n; ++i) {
long long x; cin>>x;
if(x>t) v[i]=-1;
else v[i]=t-x+1;
}
priority_queue<pair<long long,tuple<long long,long long,long long>>> q;
auto [a,b] = opt(0,n);
auto [l,m] = a;
long long init = n-l;
q.push({m,{b,0,n}});
for (long long i = 0; i < d; ++i) {
auto [a,b] = q.top(); q.pop();
auto [p,l,r] = b;
init-=a;
auto [u,v] = opt(l,p+1);
auto [u2,v2] = opt(p+1,r);
q.push({u.second,{v,l,p+1}});
q.push({u2.second,{v2,p+1,r}});
}
cout<<init<<endl;
}