oj.uz

Submission #871477

# Submission time Handle Problem Language Result Execution time Memory
871477 2023-11-11T01:56:34 Z resting Chorus (JOI23_chorus) C++17
0 / 100
 193 ms 626572 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 = 1e9;
    double res = 0, m = 0; long double m2 = 0;
    int cnt = 0;
    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;
        for(int i = 0; i < 2 * n; i++){
            if(s[i] == 'A'){
                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(-sl, tmp.first + sl*cnta - cur, tmp.second);
            }
            else{
                sl++;
            }
        }
        if(cnt < k) r = m;
        else l = m;
    }
    cout<<(int)round(res-m*cnt)<<endl;
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:40:40: warning: unused variable 'm2' [-Wunused-variable]
   40 |     double res = 0, m = 0; long double m2 = 0;
      |                                        ^~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 626496 KB Output is correct
2 Correct 107 ms 626528 KB Output is correct
3 Correct 107 ms 626572 KB Output is correct
4 Incorrect 110 ms 626516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 626496 KB Output is correct
2 Correct 107 ms 626528 KB Output is correct
3 Correct 107 ms 626572 KB Output is correct
4 Incorrect 110 ms 626516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 626496 KB Output is correct
2 Correct 107 ms 626528 KB Output is correct
3 Correct 107 ms 626572 KB Output is correct
4 Incorrect 110 ms 626516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 626496 KB Output is correct
2 Correct 107 ms 626528 KB Output is correct
3 Correct 107 ms 626572 KB Output is correct
4 Incorrect 110 ms 626516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 626496 KB Output is correct
2 Correct 107 ms 626528 KB Output is correct
3 Correct 107 ms 626572 KB Output is correct
4 Incorrect 110 ms 626516 KB Output isn't correct
5 Halted 0 ms 0 KB -