Submission #825421

#	Time	Username	Problem	Language	Result	Execution time	Memory
825421		grogu	Chorus (JOI23_chorus)	C++14	0 / 100	3 ms	5028 KiB

chorus

    #define here cerr<<"===========================================\n"
    #define dbg(x) cerr<<#x<<": "<<x<<endl;
    #include <bits/stdc++.h>
    #define ld double
    #define ll int64_t
    #define ull unsigned long long
    #define llinf 100000000000000000LL // 10^17
    #define iinf 2000000000 // 2*10^9
    #define pb push_back
    #define eb emplace_back
    #define popb pop_back
    #define fi first
    #define sc second
    #define endl '\n'
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define pld pair<ld,ld>
    #define all(a) a.begin(),a.end()
    #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
    #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
    #define si(a) (ll)(a.size())
    using namespace std;
     
     
    #define maxn 100005
    ll n,k;
    ll a[2*maxn];
    ll c[maxn];
    ll ps[maxn];
    ll sz = 0;
    ll dp[maxn];
    struct line{
        ll n,k,cnti;
        line(){n = llinf;k = 0;cnti = 0;}
        line(ll n_,ll k_,ll cnti_){n = n_,k = k_,cnti = cnti_;}
        ll operator()(ll x){
            return k*x+n;
        }
    };
    line t[2*maxn];
    ll ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
    void init(ll &v,ll tl,ll tr){
        if(!v) v = ++tsz;
        t[v] = line();
        if(tl==tr) return;
        ll mid = (tl+tr)/2;
        init(ls[v],tl,mid);
        init(rs[v],mid+1,tr);
    }
    void upd(ll v,ll tl,ll tr,line f){
        line g = t[v];
        if(tl==tr){
            if(f(tl)<g(tl)) t[v] = f;
            return;
        }
        ll mid = (tl+tr)/2;
        if(f(tl)>g(tl)) swap(f,g);
        if(f(mid)<=g(mid)){t[v] = f;upd(rs[v],mid+1,tr,g);}
        else{t[v] = g;upd(ls[v],tl,mid,f);}
    }
    line mini(line f,line g,ll i){
        if(f(i)<g(i)) return f;
        return g;
    }
    line get(ll v,ll tl,ll tr,ll i){
        if(tl==tr) return t[v];
        ll mid = (tl+tr)/2;
        if(i<=mid) return mini(get(ls[v],tl,mid,i),t[v],i);
        return mini(get(rs[v],mid+1,tr,i),t[v],i);
    }
    ll cnt[maxn];
    ll check(ll x){
        multiset<pll> s;
        init(root,1,n);
        ll e = 1;
        s.insert({0,0});
        dp[0] = 0;
        cnt[0] = 0;
        for(ll i = 1;i<=n;i++){
            while(e<=i&&c[e]<=i){
                s.erase(s.find({dp[e-1],cnt[e-1]}));
                line f(ps[e-1]+dp[e-1],-e,cnt[e-1]);
                upd(root,1,n,f);
                e++;
            }
            dp[i] = llinf; cnt[i] = 0;
            if(si(s)){
                dp[i] = (*s.begin()).fi + x;
                cnt[i] = (*s.begin()).sc + 1;
            }
            line f = get(root,1,n,i);
            if(f(i) - ps[e-1] + e*i + x < dp[i]){
                dp[i] = f(i) - ps[e-1] + e*i + x;
                cnt[i] = f.cnti+1;
            }
            s.insert({dp[i],cnt[i]});
        }
     
        return cnt[n];
    }
    ll bs(){
        ll l = 0,r = llinf/100,mid,rez = 0;
        while(l<=r){
            mid = (l+r)/2;
            ll e = check(mid);
            if(e<k){
                r = mid-1;
            }else{
                rez = mid;
                l = mid+1;
            }
        }
        check(rez);
        return dp[n]-cnt[n]*rez;
    }
    int main(){
    	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
        cin >> n >> k;
        string s; cin >> s;
        for(ll i = 1;i<=2*n;i++){
            if(s[i-1]=='A') a[i] = 1;
        }
        ll b = 0;
        for(ll i = 2*n;i>=1;i--){
            if(a[i]==1){
                c[++sz] = b;
            }else b++;
        }
        for(ll i = 1;i<=n;i++) ps[i] = ps[i-1] + c[i];
        //for(ll i = 0;i<=n;i++) ceri(dp[i],0,k);
        cout<<bs()<<endl;
    	return (0-0);
    }
    /**
    5 2
    AABABABBAB
     
    **/

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