Submission #855323

#TimeUsernameProblemLanguageResultExecution timeMemory
855323willychanChorus (JOI23_chorus)C++14
0 / 100
0 ms2396 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; //#include<bits/extc++.h> //__gnu_pbds const int N = 1e5+5; pair<ll,int> dp[N]; int Bpa[N]; ll Bpasum[N]; int n,K; ll cost(int i,int j){ int l = i; int r = j+1; while(r-l>1){ int mid = (l+r)/2; if(Bpa[mid]<j) l = mid; else r = mid; } int cnt = l-i; ll ans = Bpasum[l]-Bpasum[i]; return cnt*j-ans; } struct seg{ int pos;int l;int r; seg(int _pos,int _l,int _r):pos(_pos),l(_l),r(_r){} }; bool ok(int v){ for(int i=0;i<=n;i++) dp[i] = {1e18,0}; dp[0]={0,0}; dp[n+1] = {1e15,0}; deque<seg> dq; dq.push_back(seg(0,1,n)); for(int i=1;i<=n;i++){ while(dq.size()){ if(dq[0].r<i) dq.pop_front(); else break; } dp[i] = {dp[dq[0].pos].first+cost(dq[0].pos,i)+v,dp[dq[0].pos].second+1}; while(dq.size()){ if(dp[dq.back().pos].first+cost(dq.back().pos,dq.back().l)>dp[i].first+cost(i,dq.back().l)) dq.pop_back(); else break; } if(dq.empty()) dq.push_back(seg(i,i+1,n)); else{ seg pseg = dq.back(); dq.pop_back(); int l = pseg.l;int r = pseg.r+1; while(r-l>1){ int mid = (l+r)/2; if(dp[pseg.pos].first+cost(pseg.pos,mid)>dp[i].first+cost(i,mid)) r=mid; else l = mid; } dq.push_back(seg(pseg.pos,pseg.l,l)); if(l!=n) dq.push_back(seg(i,l+1,n)); } } //cout<<(dp[n].second<=K)<<" "<<dp[n].first<<" "<<v<<"\n"; return (dp[n].second<=K); } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>K; string s;cin>>s; int pa = 0; int pb = 0; for(int i=1;i<=2*n;i++){ if(s[i-1]=='A') pa++; if(s[i-1]=='B') Bpa[++pb]=pa; } for(int i=1;i<=n;i++){ Bpasum[i] = Bpasum[i-1]+Bpa[i]; } ll l = -1;ll r = 1e12; while(r-l>1){ ll mid = l+((r-l)/2); if(ok(mid)) r = mid; else l = mid; } ok(r); //cout<<r<<"\n"; cout<<dp[n].first-r*K<<"\n"; 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...