oj.uz

Submission #932335

# Submission time Handle Problem Language Result Execution time Memory
932335 2024-02-23T08:23:35 Z alextodoran Chorus (JOI23_chorus) C++17
0 / 100
 1 ms 4696 KB 
/**
 _  _   __  _ _ _  _  _ _
 |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];

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

ll solve (ld pen) {
    build();
    deque <int> rel;
    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]) >= f(rel[1])) {
            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 * cnt[N]);
}

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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -