답안 #871491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871491	2023-11-11T03:44:50 Z	resting	Chorus (JOI23_chorus)	C++17	16 / 100	201 ms	626632 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 = 0, r = 1e6;
    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-6){
        m = (l + r) / 2;
        memsz = 0;
        segtree ac(0, n);
        long double sl = 0;
        ac.u(0, 0, 0);
        int cnta = 0;
        long 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 + max(0LL, b[cnta-1] - i - cntactive))*cnta-funnynumber, tmp.second);
            }
            else{
                cntactive--;
                sl++;
            }
        }
        if(cnt < k) r = m;
        else l = m;
    }
    //cout<<cnt<<","<<k<<endl;
    cout<<(int)round(res-m*k)<<endl;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	626512 KB	Output is correct
2	Correct	109 ms	626628 KB	Output is correct
3	Correct	112 ms	626516 KB	Output is correct
4	Correct	111 ms	626520 KB	Output is correct
5	Correct	108 ms	626516 KB	Output is correct
6	Correct	107 ms	626632 KB	Output is correct
7	Correct	101 ms	626512 KB	Output is correct
8	Correct	103 ms	626540 KB	Output is correct
9	Correct	103 ms	626516 KB	Output is correct
10	Correct	101 ms	626576 KB	Output is correct
11	Correct	102 ms	626452 KB	Output is correct
12	Correct	100 ms	626508 KB	Output is correct
13	Correct	103 ms	626496 KB	Output is correct
14	Correct	100 ms	626564 KB	Output is correct
15	Correct	101 ms	626512 KB	Output is correct
16	Correct	102 ms	626516 KB	Output is correct

Subtask #2
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	626512 KB	Output is correct
2	Correct	109 ms	626628 KB	Output is correct
3	Correct	112 ms	626516 KB	Output is correct
4	Correct	111 ms	626520 KB	Output is correct
5	Correct	108 ms	626516 KB	Output is correct
6	Correct	107 ms	626632 KB	Output is correct
7	Correct	101 ms	626512 KB	Output is correct
8	Correct	103 ms	626540 KB	Output is correct
9	Correct	103 ms	626516 KB	Output is correct
10	Correct	101 ms	626576 KB	Output is correct
11	Correct	102 ms	626452 KB	Output is correct
12	Correct	100 ms	626508 KB	Output is correct
13	Correct	103 ms	626496 KB	Output is correct
14	Correct	100 ms	626564 KB	Output is correct
15	Correct	101 ms	626512 KB	Output is correct
16	Correct	102 ms	626516 KB	Output is correct
17	Incorrect	102 ms	626408 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	626512 KB	Output is correct
2	Correct	109 ms	626628 KB	Output is correct
3	Correct	112 ms	626516 KB	Output is correct
4	Correct	111 ms	626520 KB	Output is correct
5	Correct	108 ms	626516 KB	Output is correct
6	Correct	107 ms	626632 KB	Output is correct
7	Correct	101 ms	626512 KB	Output is correct
8	Correct	103 ms	626540 KB	Output is correct
9	Correct	103 ms	626516 KB	Output is correct
10	Correct	101 ms	626576 KB	Output is correct
11	Correct	102 ms	626452 KB	Output is correct
12	Correct	100 ms	626508 KB	Output is correct
13	Correct	103 ms	626496 KB	Output is correct
14	Correct	100 ms	626564 KB	Output is correct
15	Correct	101 ms	626512 KB	Output is correct
16	Correct	102 ms	626516 KB	Output is correct
17	Incorrect	102 ms	626408 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	626512 KB	Output is correct
2	Correct	109 ms	626628 KB	Output is correct
3	Correct	112 ms	626516 KB	Output is correct
4	Correct	111 ms	626520 KB	Output is correct
5	Correct	108 ms	626516 KB	Output is correct
6	Correct	107 ms	626632 KB	Output is correct
7	Correct	101 ms	626512 KB	Output is correct
8	Correct	103 ms	626540 KB	Output is correct
9	Correct	103 ms	626516 KB	Output is correct
10	Correct	101 ms	626576 KB	Output is correct
11	Correct	102 ms	626452 KB	Output is correct
12	Correct	100 ms	626508 KB	Output is correct
13	Correct	103 ms	626496 KB	Output is correct
14	Correct	100 ms	626564 KB	Output is correct
15	Correct	101 ms	626512 KB	Output is correct
16	Correct	102 ms	626516 KB	Output is correct
17	Incorrect	102 ms	626408 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	626512 KB	Output is correct
2	Correct	109 ms	626628 KB	Output is correct
3	Correct	112 ms	626516 KB	Output is correct
4	Correct	111 ms	626520 KB	Output is correct
5	Correct	108 ms	626516 KB	Output is correct
6	Correct	107 ms	626632 KB	Output is correct
7	Correct	101 ms	626512 KB	Output is correct
8	Correct	103 ms	626540 KB	Output is correct
9	Correct	103 ms	626516 KB	Output is correct
10	Correct	101 ms	626576 KB	Output is correct
11	Correct	102 ms	626452 KB	Output is correct
12	Correct	100 ms	626508 KB	Output is correct
13	Correct	103 ms	626496 KB	Output is correct
14	Correct	100 ms	626564 KB	Output is correct
15	Correct	101 ms	626512 KB	Output is correct
16	Correct	102 ms	626516 KB	Output is correct
17	Incorrect	102 ms	626408 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

답안 #871491

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