답안 #871551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871551	2023-11-11T05:35:25 Z	resting	Chorus (JOI23_chorus)	C++17	16 / 100	92 ms	626624 KB

chorus

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

#define int long long

struct segtree{
    int l, r, i; int 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(int qm, int 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<int, int> q(int qi){
        pair<int, 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++];}
int n, k; 
int res = 0;
int cnt = 0;string s; 
vector<int> b;
void solve(int m){
    segtree ac(0, n);
    int sl = 0;
    ac.u(0, 0, 0);
    int cnta = 0;
    int 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++;
        }
    }
}
signed main(){
    cin >> n >> k;
    cin >> s;
    int l = 0, r = 2e12;
    int m = 0; 
    for(int i = 0; i < 2*n; i++){
        if(s[i] == 'B') b.push_back(i);
    }
    while(r - l > 1){
        m = (l+r)/2;
        solve(m);
        if(cnt <= k) r = m;
        else l = m;
    }
    solve(r);
    cout<<res-k*r<<endl;
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	626584 KB	Output is correct
2	Correct	85 ms	626512 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	89 ms	626612 KB	Output is correct
5	Correct	89 ms	626512 KB	Output is correct
6	Correct	88 ms	626556 KB	Output is correct
7	Correct	84 ms	626620 KB	Output is correct
8	Correct	83 ms	626512 KB	Output is correct
9	Correct	83 ms	626516 KB	Output is correct
10	Correct	84 ms	626580 KB	Output is correct
11	Correct	87 ms	626504 KB	Output is correct
12	Correct	86 ms	626512 KB	Output is correct
13	Correct	85 ms	626436 KB	Output is correct
14	Correct	92 ms	626624 KB	Output is correct
15	Correct	90 ms	626444 KB	Output is correct
16	Correct	84 ms	626588 KB	Output is correct

Subtask #2

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	626584 KB	Output is correct
2	Correct	85 ms	626512 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	89 ms	626612 KB	Output is correct
5	Correct	89 ms	626512 KB	Output is correct
6	Correct	88 ms	626556 KB	Output is correct
7	Correct	84 ms	626620 KB	Output is correct
8	Correct	83 ms	626512 KB	Output is correct
9	Correct	83 ms	626516 KB	Output is correct
10	Correct	84 ms	626580 KB	Output is correct
11	Correct	87 ms	626504 KB	Output is correct
12	Correct	86 ms	626512 KB	Output is correct
13	Correct	85 ms	626436 KB	Output is correct
14	Correct	92 ms	626624 KB	Output is correct
15	Correct	90 ms	626444 KB	Output is correct
16	Correct	84 ms	626588 KB	Output is correct
17	Incorrect	92 ms	626516 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	626584 KB	Output is correct
2	Correct	85 ms	626512 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	89 ms	626612 KB	Output is correct
5	Correct	89 ms	626512 KB	Output is correct
6	Correct	88 ms	626556 KB	Output is correct
7	Correct	84 ms	626620 KB	Output is correct
8	Correct	83 ms	626512 KB	Output is correct
9	Correct	83 ms	626516 KB	Output is correct
10	Correct	84 ms	626580 KB	Output is correct
11	Correct	87 ms	626504 KB	Output is correct
12	Correct	86 ms	626512 KB	Output is correct
13	Correct	85 ms	626436 KB	Output is correct
14	Correct	92 ms	626624 KB	Output is correct
15	Correct	90 ms	626444 KB	Output is correct
16	Correct	84 ms	626588 KB	Output is correct
17	Incorrect	92 ms	626516 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	626584 KB	Output is correct
2	Correct	85 ms	626512 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	89 ms	626612 KB	Output is correct
5	Correct	89 ms	626512 KB	Output is correct
6	Correct	88 ms	626556 KB	Output is correct
7	Correct	84 ms	626620 KB	Output is correct
8	Correct	83 ms	626512 KB	Output is correct
9	Correct	83 ms	626516 KB	Output is correct
10	Correct	84 ms	626580 KB	Output is correct
11	Correct	87 ms	626504 KB	Output is correct
12	Correct	86 ms	626512 KB	Output is correct
13	Correct	85 ms	626436 KB	Output is correct
14	Correct	92 ms	626624 KB	Output is correct
15	Correct	90 ms	626444 KB	Output is correct
16	Correct	84 ms	626588 KB	Output is correct
17	Incorrect	92 ms	626516 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	626584 KB	Output is correct
2	Correct	85 ms	626512 KB	Output is correct
3	Correct	85 ms	626516 KB	Output is correct
4	Correct	89 ms	626612 KB	Output is correct
5	Correct	89 ms	626512 KB	Output is correct
6	Correct	88 ms	626556 KB	Output is correct
7	Correct	84 ms	626620 KB	Output is correct
8	Correct	83 ms	626512 KB	Output is correct
9	Correct	83 ms	626516 KB	Output is correct
10	Correct	84 ms	626580 KB	Output is correct
11	Correct	87 ms	626504 KB	Output is correct
12	Correct	86 ms	626512 KB	Output is correct
13	Correct	85 ms	626436 KB	Output is correct
14	Correct	92 ms	626624 KB	Output is correct
15	Correct	90 ms	626444 KB	Output is correct
16	Correct	84 ms	626588 KB	Output is correct
17	Incorrect	92 ms	626516 KB	Output isn't correct
18	Halted	0 ms	0 KB	-