Submission #1007259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007259		snpmrnhlol	Chorus (JOI23_chorus)	C++17	100 / 100	1682 ms	58416 KiB

chorus

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6;
const ll inf = 1e18;
char v[N*2];
int v2[N],v3[N];
ll ps[N + 1];
pair<ll,int> dp[N + 1];
int n,k;
int cnt = 0,cnt2 = 0;
struct line{
    ll k,b;
    int id;
};
bool check(line a,line b,line c){
    return (a.b - b.b)*(b.k - c.k) <= (b.b - c.b)*(a.k - b.k);
}
struct CHT{
    vector <line> cht;
    int sz = 0, pt = 0;
    void init(){
        cht.clear();
        sz = 0;
        pt = 0;
    }
    void add(ll k,ll b,int id){
        while(sz >= 2 && check(cht[sz - 2],cht[sz - 1],{k,b,id})){
            cht.pop_back();
            sz--;
        }
        cht.push_back({k,b,id});
        pt = min(pt,sz - 1);
        sz++;
    }
    pair<ll,int> get(int x){
        assert(sz != 0);
        pt = max(pt,0);
        while(pt < sz - 1 && x > -(cht[pt].b - cht[pt + 1].b)/(cht[pt].k - cht[pt + 1].k)){
            pt++;
        }
        return {cht[pt].k*x + cht[pt].b,cht[pt].id};
    }
};
CHT cht;
pair <ll,int> check(ll x){
    dp[0] = {0,0};
    cht.init();
    int pt = 0;
    for(int i = 1;i <= n;i++){
        dp[i] = {inf,0};
        while(pt < i && max(v2[pt],pt) < i){
            cht.add(-pt,dp[pt].first + x - 1ll*max(v2[pt],pt)*(n - pt) + ps[max(v2[pt],pt)],dp[pt].second);
            pt++;
        }
        if(pt != i){
            dp[i] = min(dp[i],{dp[pt].first + x,dp[pt].second + 1});
        }
        if(cht.sz != 0){
            auto id = cht.get(i);
            dp[i] = min(dp[i],{id.first + 1ll*i*n - ps[i],id.second + 1});
        }
    }
    return dp[n];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i = 0;i < 2*n;i++){
        cin>>v[i];
        if(v[i] == 'B'){
            v2[cnt] = i - cnt;
            cnt++;
        }
        if(v[i] == 'A'){
            v3[cnt2] = i - cnt2;
            cnt2++;
        }
    }
    for(int i = 1;i <= n;i++){
        ps[i] = ps[i - 1] + (n - v3[i - 1]);
    }
    ll l = 0,r = inf;
    ll ans = 0;
    while(l != r){
        ll mij = (l + r)/2;
        auto x = check(mij);
        if(x.second >= k){
            l = mij + 1;
        }else{
            r = mij;
        }
    }
    check(l);
    ans = dp[n].first - k*l;
    cout<<ans;
    return 0;
}

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