Submission #798938

#	Time	Username	Problem	Language	Result	Execution time	Memory
798938		finn__	Chorus (JOI23_chorus)	C++17	61 / 100	950 ms	1096 KiB

chorus

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

struct linear_fn
{
    int64_t m, t;
    linear_fn(int64_t m, int64_t t) { this->m = m, this->t = t; }
    int64_t operator()(int64_t x) { return m * x + t; }
    bool intersects_earlier(linear_fn const &f, linear_fn const &g)
    {
        return (__int128_t)(f.t - t) * (m - g.m) < (__int128_t)(m - f.m) * (g.t - t);
    }
};

constexpr size_t N = 5001;

int64_t p[N], b[N], f[N], u[N], j_[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, k;
    string s;
    cin >> n >> k >> s;

    for (size_t i = 1, j = 1, l = 1; i <= n << 1; ++i)
    {
        if (s[i - 1] == 'B')
            b[j++] = i;
        else
            p[l++] = j;
    }

    for (size_t i = 1; i <= n; ++i)
        j_[i] = max<int64_t>(i, lower_bound(p + 1, p + n + 1, i) - p);

    for (size_t i = 1; i <= n; ++i)
        p[i] += p[i - 1];

    auto dp = [&](int64_t const lambda)
    {
        fill(f + 1, f + N, INT64_MAX);
        for (int64_t i = 1; i <= n; ++i)
            for (int64_t j = 0; j < i; ++j)
                if (f[j] != INT64_MAX)
                {
                    int64_t j__ = min(i + 1, j_[j + 1]),
                            val = f[j] + p[i] - p[j__ - 1] - (i - j__ + 1) * (j + 1) + lambda;
                    if (val < f[i])
                        f[i] = val, u[i] = u[j] + 1;
                }
        return make_pair(f[n], u[n]);
    };

    int64_t a = 0, b = 1LL << 42;
    while (a < b)
    {
        int64_t lambda = (a + b) / 2;
        auto [val, used] = dp(lambda);
        if (used > k)
            a = lambda + 1;
        else
            b = lambda;
    }

    auto val = dp(a).first;
    cout << val - (int64_t)k * a << '\n';
}

Compilation message (stderr)

chorus.cpp: In lambda function:
chorus.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int64_t i = 1; i <= n; ++i)
      |                             ~~^~~~
chorus.cpp: In function 'int main()':
chorus.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<long int, long int> >::type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if (used > k)
      |             ~~~~~^~~

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