Submission #798946

#	Time	Username	Problem	Language	Result	Execution time	Memory
798946		finn__	Chorus (JOI23_chorus)	C++17	61 / 100	821 ms	1216 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__ = 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:35: 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:22: 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