oj.uz

Submission #871515

# Submission time Handle Problem Language Result Execution time Memory
871515 2023-11-11T04:47:30 Z resting Chorus (JOI23_chorus) C++17
0 / 100
 7000 ms 626516 KB 
#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/k;
    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-5){
        m = sqrt(l*r);
        memsz = 0;
        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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7058 ms 626516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7058 ms 626516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7058 ms 626516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7058 ms 626516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7058 ms 626516 KB Time limit exceeded
2 Halted 0 ms 0 KB -