제출 #863116

#제출 시각아이디문제언어결과실행 시간메모리
863116KiaRezThe short shank; Redemption (BOI21_prison)C++17
35 / 100
15 ms12888 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 5e5+23, lg = 19; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, d, T, t[N], ans, seg[4*N], res[N], l[N]; void update(int ind, int val) { if(ind == 0) return; if(ind >= (1<<lg)) { seg[ind] = val; } else { seg[ind] = min(seg[2*ind], seg[2*ind+1]); } update(ind/2, val); } int find(int val, int ind=1) { if(seg[ind] > val) return 0; if(ind >= (1<<lg)) { return (ind-(1<<lg)+1); } if(seg[2*ind+1] <= val) return find(val, 2*ind+1); return find(val, 2*ind); } int main () { ios_base::sync_with_stdio(false), cin.tie(0); cin>>n>>d>>T; if(n>4000) kill(0); for(int i=1; i<=n; i++) { cin>>t[i]; } fill(seg, seg+4*N, (int)2e9); for(int i=1; i<=n; i++) { update(i+(1<<lg)-1, t[i]-i); int j = find(T-i); if(j==0) { ans++; } else { l[i] = j+1; } } for(int i=1; i<=d; i++) { for(int j=1; j<=n; j++) { if(l[j] == 0) continue; res[l[j]] ++; res[j+1]--; } for(int j=1; j<=n; j++) { res[j] += res[j-1]; } int maxi = 0; for(int j=1; j<=n; j++) { if(res[j]>=res[maxi]) maxi = j; } ans += res[maxi]; fill(res, res+n+2, 0); for(int j=1; j<=n; j++) { if(l[j] == 0) continue; if(l[j] <= maxi && maxi <= j) { l[j] = 0; } } } cout<<n - ans<<endl; return 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...