Submission #871519

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871519	2023-11-11T04:50:31 Z	resting	Chorus (JOI23_chorus)	C++17	16 / 100	89 ms	626688 KB

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 = 1, 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);
        if(r-l < 1e-3)break;
        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
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	626516 KB	Output is correct
2	Correct	87 ms	626568 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	85 ms	626516 KB	Output is correct
5	Correct	85 ms	626472 KB	Output is correct
6	Correct	84 ms	626460 KB	Output is correct
7	Correct	88 ms	626688 KB	Output is correct
8	Correct	86 ms	626560 KB	Output is correct
9	Correct	86 ms	626524 KB	Output is correct
10	Correct	84 ms	626512 KB	Output is correct
11	Correct	86 ms	626592 KB	Output is correct
12	Correct	87 ms	626624 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	84 ms	626516 KB	Output is correct
15	Correct	84 ms	626512 KB	Output is correct
16	Correct	86 ms	626512 KB	Output is correct

Subtask #2
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	626516 KB	Output is correct
2	Correct	87 ms	626568 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	85 ms	626516 KB	Output is correct
5	Correct	85 ms	626472 KB	Output is correct
6	Correct	84 ms	626460 KB	Output is correct
7	Correct	88 ms	626688 KB	Output is correct
8	Correct	86 ms	626560 KB	Output is correct
9	Correct	86 ms	626524 KB	Output is correct
10	Correct	84 ms	626512 KB	Output is correct
11	Correct	86 ms	626592 KB	Output is correct
12	Correct	87 ms	626624 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	84 ms	626516 KB	Output is correct
15	Correct	84 ms	626512 KB	Output is correct
16	Correct	86 ms	626512 KB	Output is correct
17	Incorrect	89 ms	626640 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	626516 KB	Output is correct
2	Correct	87 ms	626568 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	85 ms	626516 KB	Output is correct
5	Correct	85 ms	626472 KB	Output is correct
6	Correct	84 ms	626460 KB	Output is correct
7	Correct	88 ms	626688 KB	Output is correct
8	Correct	86 ms	626560 KB	Output is correct
9	Correct	86 ms	626524 KB	Output is correct
10	Correct	84 ms	626512 KB	Output is correct
11	Correct	86 ms	626592 KB	Output is correct
12	Correct	87 ms	626624 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	84 ms	626516 KB	Output is correct
15	Correct	84 ms	626512 KB	Output is correct
16	Correct	86 ms	626512 KB	Output is correct
17	Incorrect	89 ms	626640 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	626516 KB	Output is correct
2	Correct	87 ms	626568 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	85 ms	626516 KB	Output is correct
5	Correct	85 ms	626472 KB	Output is correct
6	Correct	84 ms	626460 KB	Output is correct
7	Correct	88 ms	626688 KB	Output is correct
8	Correct	86 ms	626560 KB	Output is correct
9	Correct	86 ms	626524 KB	Output is correct
10	Correct	84 ms	626512 KB	Output is correct
11	Correct	86 ms	626592 KB	Output is correct
12	Correct	87 ms	626624 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	84 ms	626516 KB	Output is correct
15	Correct	84 ms	626512 KB	Output is correct
16	Correct	86 ms	626512 KB	Output is correct
17	Incorrect	89 ms	626640 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	626516 KB	Output is correct
2	Correct	87 ms	626568 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	85 ms	626516 KB	Output is correct
5	Correct	85 ms	626472 KB	Output is correct
6	Correct	84 ms	626460 KB	Output is correct
7	Correct	88 ms	626688 KB	Output is correct
8	Correct	86 ms	626560 KB	Output is correct
9	Correct	86 ms	626524 KB	Output is correct
10	Correct	84 ms	626512 KB	Output is correct
11	Correct	86 ms	626592 KB	Output is correct
12	Correct	87 ms	626624 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	84 ms	626516 KB	Output is correct
15	Correct	84 ms	626512 KB	Output is correct
16	Correct	86 ms	626512 KB	Output is correct
17	Incorrect	89 ms	626640 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Submission #871519

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0