제출 #1007112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1007112		snpmrnhlol	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	6492 KiB

chorus

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 1e18;
char v[N*2];
ll v2[N],v3[N];
ll ps[N + 1];
pair<ll,ll> dp[N + 1];
ll n,k;
ll cnt = 0,cnt2 = 0;
struct line{
    ll k,b;
};
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;
    ll sz = 0, pt = 0;
    void init(){
        cht.clear();
        sz = 0;
        pt = 0;
    }
    void add(ll k,ll b){
        while(sz >= 2 && check(cht[cnt - 2],cht[cnt - 1],{k,b})){
            cht.pop_back();
            sz--;
        }
        cht.push_back({k,b});
        sz++;
    }
    ll get(ll x){
        pt = min(pt,sz - 1);
        while(pt < sz - 1 && x*(cht[pt].k - cht[pt + 1].k) <= -(cht[pt].b - cht[pt + 1].b)){
            pt++;
        }
        return cht[pt].k*x + cht[pt].b;
    }
};
pair <ll,ll> check(ll x){
    //cout<<"checking:"<<x<<'\n';
    dp[0] = {0,0};
    for(ll i = 1;i <= n;i++){
        dp[i] = {inf,0};
        for(ll j = i - 1;j >= 0;j--){
            if(v2[j] >= i){
                dp[i] = min(dp[i],{dp[j].first + x,dp[j].second + 1});
                //cout<<i<<"->"<<j<<' '<<dp[j].first + x<<' '<<dp[j].second + 1<<'\n';
            }else{
                dp[i] = min(dp[i],{dp[j].first + x + (i - v2[j])*(n - j) - (ps[i] - ps[v2[j]]),dp[j].second + 1});
                //cout<<i<<"->"<<j<<' '<<dp[j].first<<' '<<x<<' '<<(i - v2[j])*(n - j)<<' '<<(ps[i] - ps[v2[j]])<<' '<<dp[j].second + 1<<'\n';
            }
        }
        //cout<<dp[i].first<<' '<<dp[i].second<<' '<<x<<' '<<i<<'\n';
    }
    return dp[n];
    //cout<<'\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(ll 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(ll 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;
            ans = dp[n].first - dp[n].second*mij;
        }
    }
    cout<<ans;
    return 0;
}

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