답안 #932352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932352	2024-02-23T08:39:02 Z	alextodoran	Chorus (JOI23_chorus)	C++17	40 / 100	900 ms	7000 KB

chorus

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N_MAX = 2000000;
const ll INF = LLONG_MAX;
const ld EPS = 1e-9;

int N, K;
int A[N_MAX + 2];

struct SegInfo {
    ll first; int rate;
};
SegInfo seg_tree[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    seg_tree[node] = SegInfo{0, 0};
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    build(left, l, mid);
    build(right, mid + 1, r);
}
void build () {
    build(1, 1, N);
}

void split (int node, int l, int r) {
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].first += seg_tree[node].first + (ll) (r - mid) * seg_tree[node].rate;
    seg_tree[left].rate += seg_tree[node].rate;
    seg_tree[right].first += seg_tree[node].first;
    seg_tree[right].rate += seg_tree[node].rate;
    seg_tree[node].first = seg_tree[node].rate = 0;
}

void update (int node, int l, int r, int pos, ll first) {
    if (r <= pos) {
        seg_tree[node].first += first + (pos - r);
        seg_tree[node].rate++;
        return;
    }
    split(node, l, r);
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    update(left, l, mid, pos, first);
    if (mid + 1 <= pos) {
        update(right, mid + 1, r, pos, first);
    }
}
void update (int pos, int first) {
    update(1, 1, N, pos, first);
}

ll query (int node, int l, int r, int pos) {
    if (l == r) {
        return seg_tree[node].first;
    }
    split(node, l, r);
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    if (pos <= mid) {
        return query(left, l, mid, pos);
    } else {
        return query(right, mid + 1, r, pos);
    }
}
ll query (int pos) {
    return query(1, 1, N, pos);
}

ld dp[N_MAX + 2];
int cnt[N_MAX + 2];

deque <int> rel;

pair <ld, int> f (int j) {
    return make_pair(dp[j] + query(j + 1), cnt[j]);
}

pair <ld, int> get_min () {
    pair <ld, int> mn = f(rel[1]);
    for (int i = 2; i < min((int) rel.size(), 10); i++) {
        mn = min(mn, f(rel[i]));
    }
    return mn;
}

ll solve (ld pen) {
    build();
    rel.clear();
    for (int i = 1; i <= N; i++) {
        if (A[i] - i + 1 <= i) {
            update(A[i] - i + 1, 0);
        } else {
            update(i, (A[i] - i + 1) - i);
        }
        while (rel.empty() == false && f(i - 1) <= f(rel.back())) {
            rel.pop_back();
        }
        rel.push_back(i - 1);
        while ((int) rel.size() >= 2 && f(rel[0]) >= get_min()) {
            rel.pop_front();
        }
        if (rel.empty() == true) {
            dp[i] = INF;
        } else {
            tie(dp[i], cnt[i]) = f(rel.front());
            dp[i] += pen; cnt[i]++;
        }
    }
    return (ll) round(dp[N] - pen * K);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(2);

    cin >> N >> K;
    string S;
    cin >> S;
    for (int i = 0, j = 0; i < N * 2; i++) {
        if (S[i] == 'A') {
            A[++j] = i + 1;
        }
    }
    ld l = 0, r = LLONG_MAX; int iter = 150;
    while (iter--) {
        ld mid = (l + r) / 2;
        solve(mid);
        if (cnt[N] <= K) {
            r = mid;
        } else {
            l = mid + EPS;
        }
    }
    cout << solve(l) << "\n";
    assert(cnt[N] <= K);

    return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	13 ms	4444 KB	Output is correct
18	Correct	45 ms	4560 KB	Output is correct
19	Correct	44 ms	4440 KB	Output is correct
20	Correct	55 ms	4560 KB	Output is correct
21	Correct	80 ms	4560 KB	Output is correct
22	Correct	39 ms	4444 KB	Output is correct
23	Correct	37 ms	4696 KB	Output is correct
24	Correct	83 ms	4444 KB	Output is correct
25	Correct	35 ms	4444 KB	Output is correct
26	Correct	39 ms	4440 KB	Output is correct
27	Correct	41 ms	4440 KB	Output is correct
28	Correct	42 ms	4444 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	13 ms	4444 KB	Output is correct
18	Correct	45 ms	4560 KB	Output is correct
19	Correct	44 ms	4440 KB	Output is correct
20	Correct	55 ms	4560 KB	Output is correct
21	Correct	80 ms	4560 KB	Output is correct
22	Correct	39 ms	4444 KB	Output is correct
23	Correct	37 ms	4696 KB	Output is correct
24	Correct	83 ms	4444 KB	Output is correct
25	Correct	35 ms	4444 KB	Output is correct
26	Correct	39 ms	4440 KB	Output is correct
27	Correct	41 ms	4440 KB	Output is correct
28	Correct	42 ms	4444 KB	Output is correct
29	Correct	630 ms	6744 KB	Output is correct
30	Correct	546 ms	7000 KB	Output is correct
31	Correct	560 ms	6744 KB	Output is correct
32	Correct	711 ms	6748 KB	Output is correct
33	Correct	874 ms	6748 KB	Output is correct
34	Correct	494 ms	6748 KB	Output is correct
35	Correct	450 ms	6748 KB	Output is correct
36	Incorrect	900 ms	6748 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	13 ms	4444 KB	Output is correct
18	Correct	45 ms	4560 KB	Output is correct
19	Correct	44 ms	4440 KB	Output is correct
20	Correct	55 ms	4560 KB	Output is correct
21	Correct	80 ms	4560 KB	Output is correct
22	Correct	39 ms	4444 KB	Output is correct
23	Correct	37 ms	4696 KB	Output is correct
24	Correct	83 ms	4444 KB	Output is correct
25	Correct	35 ms	4444 KB	Output is correct
26	Correct	39 ms	4440 KB	Output is correct
27	Correct	41 ms	4440 KB	Output is correct
28	Correct	42 ms	4444 KB	Output is correct
29	Correct	630 ms	6744 KB	Output is correct
30	Correct	546 ms	7000 KB	Output is correct
31	Correct	560 ms	6744 KB	Output is correct
32	Correct	711 ms	6748 KB	Output is correct
33	Correct	874 ms	6748 KB	Output is correct
34	Correct	494 ms	6748 KB	Output is correct
35	Correct	450 ms	6748 KB	Output is correct
36	Incorrect	900 ms	6748 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4564 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	13 ms	4444 KB	Output is correct
18	Correct	45 ms	4560 KB	Output is correct
19	Correct	44 ms	4440 KB	Output is correct
20	Correct	55 ms	4560 KB	Output is correct
21	Correct	80 ms	4560 KB	Output is correct
22	Correct	39 ms	4444 KB	Output is correct
23	Correct	37 ms	4696 KB	Output is correct
24	Correct	83 ms	4444 KB	Output is correct
25	Correct	35 ms	4444 KB	Output is correct
26	Correct	39 ms	4440 KB	Output is correct
27	Correct	41 ms	4440 KB	Output is correct
28	Correct	42 ms	4444 KB	Output is correct
29	Correct	630 ms	6744 KB	Output is correct
30	Correct	546 ms	7000 KB	Output is correct
31	Correct	560 ms	6744 KB	Output is correct
32	Correct	711 ms	6748 KB	Output is correct
33	Correct	874 ms	6748 KB	Output is correct
34	Correct	494 ms	6748 KB	Output is correct
35	Correct	450 ms	6748 KB	Output is correct
36	Incorrect	900 ms	6748 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #932352

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.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
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0