Submission #798621

#	Time	Username	Problem	Language	Result	Execution time	Memory
798621		finn__	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	2272 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 = 501;

int64_t p[N], b[N], f[N][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++] = i;
    }

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

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

    for (size_t i = 0; i < N; ++i)
        fill(f[i], f[i] + N, INT64_MAX);
    f[0][0] = 0;

    for (size_t l = 1; l <= k; ++l)
        for (int64_t i = 1; i <= n; ++i)
        {
            for (int64_t j = 0; j < i; ++j)
                if (f[l - 1][j] != INT64_MAX)
                {
                    int64_t j__ = j_[j + 1],
                            val = f[l - 1][j] + p[i] - p[j__ - 1] - (i - j__ + 1) * b[j + 1] - ((i - j__) * (i - j__ + 1)) / 2;
                    if (val < f[l][i])
                        f[l][i] = val;
                }
        }

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

    cout << f[k][n] << '\n';
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int64_t i = 1; i <= n; ++i)
      |                             ~~^~~~

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