제출 #1168627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168627		Sharky	Chorus (JOI23_chorus)	C++20	0 / 100	0 ms	328 KiB

chorus

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

const int inf = 1e18;

struct Line {
    int m, c, id;
    int eval(int x) { return m * x + c; } 
    long double intersectX(Line l) { return (long double) (c - l.c) / (l.m - m); }
};

void solve() {
    int n, K, ca = 0, cb = 0;
    string s;
    cin >> n >> K >> s;
    vector<int> b(n+1), pb(n+1, 0);
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] == 'B') cb++;
        else b[++ca] = cb;
    }
    for (int i = 1; i <= n; i++) pb[i] = pb[i - 1] + b[i];
    // for (int i = 1; i <= n; i++) cout << b[i] << " \n"[i == n];
    vector<int> nxt(n+1, 0);
    for (int i = 0; i <= n; i++) {
        nxt[i] = lower_bound(b.begin() + 1, b.begin() + n + 1, i) - b.begin();
        nxt[i] = min(nxt[i], n + 1);
        // cout << nxt[i] << " ";
    }
    // cout << '\n';
    vector<vector<int>> psh(n+2);
    for (int i = 0; i <= n; i++) psh[max(i + 1, nxt[i])].push_back(i);
    // for (int i = 0; i <= n; i++) cout << max(i + 1, nxt[i]) << " " << pb[i] << '\n';

    auto solve = [&] (int lamb) {
        // cout << lamb << " " << n << '\n';
        vector<Line> Q(n+2);
        int L = 1, R = 0;
        vector<int> dp(n+1, inf), cnt(n+1, 0);
        dp[0] = 0, cnt[0] = 0;
        // cout << "yo\n";
        auto C = [&] (int index) {
            return dp[index] - pb[max(index + 1, nxt[index]) - 1] + max(index + 1, nxt[index]) * index - index;
        };
        // Q[L] = {0, C(0), 0};
        for (int i = 1; i <= n; i++) {
            // cout << lamb << " " << i << '\n';
            for (auto& x : psh[i]) {
                // cout << "!! ins " << x << '\n';
                Line cur = {-x, C(x), x};
                while (R - L >= 1 && Q[R-1].intersectX(Q[R]) >= Q[R].intersectX(cur)) R--;
                Q[++R] = cur;
            }
            while (R - L >= 1 && Q[L].eval(i) >= Q[L+1].eval(i)) L++;
            if (L <= R) {
                // for (int j = L; j <= R; j++) cout << "line " << Q[j].m << " " << Q[j].c << '\n';
                dp[i] = Q[L].eval(i) + pb[i] - lamb, cnt[i] = cnt[Q[L].id] + 1;
            }
        }
        // for (int i = 1; i <= n; i++) cout << dp[i] << " " << cnt[i] << '\n';
        return pair<int, int>{dp[n], cnt[n]};
    };

    int l = -1e11, r = 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        pair<int, int> res = solve(mid);
        if (res.second <= K) l = mid;
        else r = mid - 1;
    }
    // int l = -1e12, r = 1;
    // while (l + 1 < r) {
    //     int mid = (l + r) / 2;
    //     pair<int, int> res = solve(mid);
    //     if (res.se <= K) l = mid;
    //     else r = mid;
    // }
    // cout << l << " " << solve(l).second << " " << solve(l).second << '\n';
    cout << solve(l).first + l * K << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13