Submission #953475

#TimeUsernameProblemLanguageResultExecution timeMemory
953475owoovoChorus (JOI23_chorus)C++17
100 / 100
4663 ms47500 KiB
#include<bits/stdc++.h> #define ll long long #define F first #define S second using namespace std; const ll maxn=1e18; ll n,k,bto[1000010],bhh[1000010],hhsum[1000010]; pair<ll,ll> dp[1000010]; ll cost(ll i,ll j){ if(i>=j)return maxn; ll l=max(i,bto[i]),r=j; return hhsum[r]-hhsum[l]-i*(r-l); } struct seg{ ll pos,l,r; seg(ll _pos,ll _l,ll _r){ pos=_pos,l=_l,r=_r; } }; bool check(ll d){ for(int i=1;i<=n;i++)dp[i]={maxn,0}; deque<seg> sg; sg.push_back({0,1,n}); for(int i=1;i<=n;i++){ while(sg.front().r<i)sg.pop_front(); ll pos=sg.front().pos; dp[i]={dp[pos].F+cost(pos,i)+d,dp[pos].S+1}; while(!sg.empty()&&dp[i].F+cost(i,sg.back().l)<dp[sg.back().pos].F+cost(sg.back().pos,sg.back().l)){ sg.pop_back(); } if(sg.empty()){ sg.push_back({i,i+1,n}); }else{ auto[pos,l,r]=sg.back(); sg.pop_back(); ll L=l,R=r; while(L!=R){ int mid=(L+R+1)>>1; if(dp[i].F+cost(i,mid)<dp[pos].F+cost(pos,mid)){ R=mid-1; }else{ L=mid; } } sg.push_back({pos,l,L}); if(L!=n)sg.push_back({i,L+1,n}); } } // for(int i=1;i<=n;i++){ // cout<<dp[i].F-d*(dp[i].S)<<" "; // } // cout<<"\n"; return dp[n].S>k; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int nowa=0,nowb=0; cin>>n>>k; for(int i=0;i<2*n;i++){ char c; cin>>c; if(c=='A'){ nowa++; bhh[nowa]=nowb; }else{ nowb++; bto[nowb]=nowa; } } for(int i=1;i<=n;i++){ hhsum[i]=hhsum[i-1]+bhh[i]; } ll l=0,r=maxn; while(l!=r){ ll m=(l+r)>>1; if(check(m)){ l=m+1; }else{ r=m; } } check(l); cout<<dp[n].F-l*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...