Submission #871543

#	Time	Username	Problem	Language	Result	Execution time	Memory
871543		resting	Chorus (JOI23_chorus)	C++17	40 / 100	122 ms	626772 KiB

chorus

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree{
    int l, r, i; double m, b; int cnt;
    segtree* lc = 0, *rc = 0;
    segtree* getmem();
    segtree(int l, int r) : l(l), r(r), m(0), b(1e9), cnt(0){
        i = (l + r) / 2;
        if(l==r) return;
        lc = getmem(); *lc = segtree(l, i);
        rc = getmem(); *rc = segtree(i+1, r);
    };
    segtree() : segtree(-1, -1){};
    void u(double qm, double qb, int qcnt){
        if(qm * i + qb < m*i+b){
            swap(m, qm); swap(b, qb); swap(cnt, qcnt);
        }
        if(l == r) return;
        if(qm > m) lc->u(qm, qb, qcnt);
        else rc->u(qm, qb, qcnt);
    }
    pair<double, int> q(int qi){
        pair<double, int> cur = {m*qi+b, cnt};
        if(i == qi) return cur;
        if(qi < i) return min(cur, lc->q(qi));
        else return min(cur, rc->q(qi));
    }

} mem[(int)1e7]; int memsz = 0; 
segtree* segtree::getmem(){return &mem[memsz++];}


signed main(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    double l = 0, r = 1e12;
    double res = 0, m = 0; 
    int cnt = 0;
    vector<int> b;
    for(int i = 0; i < 2*n; i++){
        if(s[i] == 'B') b.push_back(i);
    }
    while(r - l > 1e-3){
        m = (l+r)/2;
        segtree ac(0, n);
        double sl = 0;
        ac.u(0, 0, 0);
        int cnta = 0;
        double cur = 0;
        int funnynumber = 0;
        int cntactive = 0;
        for(int i = 0; i < 2 * n; i++){
            if(s[i] == 'A'){
                if(cntactive>0) funnynumber -= cntactive;
                cntactive++;
                if(cntactive>0) funnynumber += b[cnta] - i - cntactive;
                cnta++;
                cur += sl;
                auto tmp = ac.q(cnta); 
                tmp.first += m; tmp.second++;
                if(cnta == n) {
                    res = tmp.first + cur;
                    cnt = tmp.second;
                }
                ac.u(-cnta, tmp.first + (cnta)*cnta+funnynumber, tmp.second);
            }
            else{
                cntactive--;
                sl++;
            }
        }
        if(cnt <= k) r = m;
        else l = m;
    }
    cout<<(int)round(res-m*k)<<endl;
}

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