답안 #871520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871520	2023-11-11T04:50:51 Z	resting	Chorus (JOI23_chorus)	C++17	16 / 100	88 ms	626636 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);
        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

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	626516 KB	Output is correct
2	Correct	85 ms	626520 KB	Output is correct
3	Correct	84 ms	626628 KB	Output is correct
4	Correct	88 ms	626588 KB	Output is correct
5	Correct	84 ms	626432 KB	Output is correct
6	Correct	84 ms	626400 KB	Output is correct
7	Correct	84 ms	626508 KB	Output is correct
8	Correct	86 ms	626512 KB	Output is correct
9	Correct	88 ms	626628 KB	Output is correct
10	Correct	84 ms	626444 KB	Output is correct
11	Correct	86 ms	626636 KB	Output is correct
12	Correct	84 ms	626504 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	86 ms	626512 KB	Output is correct
15	Correct	85 ms	626508 KB	Output is correct
16	Correct	84 ms	626536 KB	Output is correct

Subtask #2
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	626516 KB	Output is correct
2	Correct	85 ms	626520 KB	Output is correct
3	Correct	84 ms	626628 KB	Output is correct
4	Correct	88 ms	626588 KB	Output is correct
5	Correct	84 ms	626432 KB	Output is correct
6	Correct	84 ms	626400 KB	Output is correct
7	Correct	84 ms	626508 KB	Output is correct
8	Correct	86 ms	626512 KB	Output is correct
9	Correct	88 ms	626628 KB	Output is correct
10	Correct	84 ms	626444 KB	Output is correct
11	Correct	86 ms	626636 KB	Output is correct
12	Correct	84 ms	626504 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	86 ms	626512 KB	Output is correct
15	Correct	85 ms	626508 KB	Output is correct
16	Correct	84 ms	626536 KB	Output is correct
17	Incorrect	83 ms	626400 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	626516 KB	Output is correct
2	Correct	85 ms	626520 KB	Output is correct
3	Correct	84 ms	626628 KB	Output is correct
4	Correct	88 ms	626588 KB	Output is correct
5	Correct	84 ms	626432 KB	Output is correct
6	Correct	84 ms	626400 KB	Output is correct
7	Correct	84 ms	626508 KB	Output is correct
8	Correct	86 ms	626512 KB	Output is correct
9	Correct	88 ms	626628 KB	Output is correct
10	Correct	84 ms	626444 KB	Output is correct
11	Correct	86 ms	626636 KB	Output is correct
12	Correct	84 ms	626504 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	86 ms	626512 KB	Output is correct
15	Correct	85 ms	626508 KB	Output is correct
16	Correct	84 ms	626536 KB	Output is correct
17	Incorrect	83 ms	626400 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	626516 KB	Output is correct
2	Correct	85 ms	626520 KB	Output is correct
3	Correct	84 ms	626628 KB	Output is correct
4	Correct	88 ms	626588 KB	Output is correct
5	Correct	84 ms	626432 KB	Output is correct
6	Correct	84 ms	626400 KB	Output is correct
7	Correct	84 ms	626508 KB	Output is correct
8	Correct	86 ms	626512 KB	Output is correct
9	Correct	88 ms	626628 KB	Output is correct
10	Correct	84 ms	626444 KB	Output is correct
11	Correct	86 ms	626636 KB	Output is correct
12	Correct	84 ms	626504 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	86 ms	626512 KB	Output is correct
15	Correct	85 ms	626508 KB	Output is correct
16	Correct	84 ms	626536 KB	Output is correct
17	Incorrect	83 ms	626400 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	626516 KB	Output is correct
2	Correct	85 ms	626520 KB	Output is correct
3	Correct	84 ms	626628 KB	Output is correct
4	Correct	88 ms	626588 KB	Output is correct
5	Correct	84 ms	626432 KB	Output is correct
6	Correct	84 ms	626400 KB	Output is correct
7	Correct	84 ms	626508 KB	Output is correct
8	Correct	86 ms	626512 KB	Output is correct
9	Correct	88 ms	626628 KB	Output is correct
10	Correct	84 ms	626444 KB	Output is correct
11	Correct	86 ms	626636 KB	Output is correct
12	Correct	84 ms	626504 KB	Output is correct
13	Correct	84 ms	626512 KB	Output is correct
14	Correct	86 ms	626512 KB	Output is correct
15	Correct	85 ms	626508 KB	Output is correct
16	Correct	84 ms	626536 KB	Output is correct
17	Incorrect	83 ms	626400 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

답안 #871520

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