Submission #925111

#	Time	Username	Problem	Language	Result	Execution time	Memory
925111		ttamx	Chorus (JOI23_chorus)	C++14	0 / 100	1 ms	4680 KiB

chorus

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;

const int N=1e6+5;

ll n,k;
string s;
ll a[N],b[N];
ll qs[N];
pl dp[N];

struct CHT{
    struct Line{
        ll m,c,cnt;
        Line(ll m,ll c,ll cnt):m(m),c(c),cnt(cnt){}
        ll get(ll x){
            return m*x+c;
        }
    };
    deque<Line> dq;
    bool bad(Line l1,Line l2,Line l3){
        return (l2.c-l1.c)*(l3.m-l1.m)<(l3.c-l1.c)*(l2.m-l1.m);
    }
    void clear(){
        dq.clear();
    }
    void insert(ll m,ll c,int cnt){
        Line l(m,c,cnt);
        while(dq.size()>1&&bad(dq.end()[-2],dq.back(),l))dq.pop_back();
        dq.emplace_back(l);
    }
    pl query(ll x){
        while(dq.size()>1&&dq[0].get(x)>dq[1].get(x))dq.pop_front();
        return pl(dq[0].get(x),dq[0].cnt);
    }
}cht;

pl solve(ll lambda){
    cht.clear();
    cht.insert(0,0,0);
    deque<int> dq;
    for(int i=1;i<=n;i++){
        while(!dq.empty()&&b[dq.front()]<i){
            int j=dq.front();
            dq.pop_front();
            cht.insert(-j,dp[j].first-qs[b[j]]+j*b[j],dp[j].second);
        }
        dp[i]=cht.query(i);
        dp[i].first+=qs[i];
        if(!dq.empty())dp[i]=min(dp[i],dp[dq.front()]);
        dp[i].first+=lambda;
        dp[i].second++;
        dq.emplace_back(i);
    }
    return dp[n];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> s;
    for(int i=0,ia=0,ib=0;i<2*n;i++){
        if(s[i]=='A'){
            a[++ia]=ib;
        }else{
            ib++;
        }
    }
    for(int i=1,p=1;i<=n;i++){
        while(p<=n&&a[p]<i)p++;
        b[i]=max(i,p-1);
    }
    for(int i=1;i<=n;i++)qs[i]=qs[i-1]+a[i];
    ll l=0,r=n*n;
    while(l<r){
        ll m=(l+r+1)/2;
        if(solve(m).second>=k)l=m;
        else r=m-1;
    }
    cout << solve(l).first-k*l;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13