Submission #925114

#	Time	Username	Problem	Language	Result	Execution time	Memory
925114		ttamx	Chorus (JOI23_chorus)	C++14	100 / 100	1630 ms	45808 KiB

chorus

#include<bits/stdc++.h>

using namespace std;

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

const int N=1e6+5;

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

struct Line{
    ll m,c,cnt;
    Line(ll _m,ll _c,ll _cnt):m(_m),c(_c),cnt(_cnt){}
    ll eval(ll x){
        return m*x+c;
    }
};

struct CHT{
    deque<Line> hull;
    bool bad(Line x,Line y,Line z){
        return (x.c-y.c)*(z.m-y.m)>(y.c-z.c)*(y.m-x.m);
    }
    void insert(ll m,ll c,ll cnt){
        Line v(m,c,cnt);
        while(hull.size()>1&&bad(hull.end()[-2],hull.back(),v))hull.pop_back();
        hull.emplace_back(v);
    }
    pl query(ll x){
        while(hull.size()>1&&hull[0].eval(x)>hull[1].eval(x))hull.pop_front();
        return pl(hull[0].eval(x),hull[0].cnt);
    }
};

pl solve(ll lambda){
    CHT cht;
    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]]+1LL*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=1LL*n*n;
    while(l<r){
        ll m=(l+r)/2;
        if(solve(m).second<=k)r=m;
        else l=m+1;
    }
    cout << solve(l).first-k*l;
}

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