oj.uz

Submission #798617

# Submission time Handle Problem Language Result Execution time Memory
798617 2023-07-30T21:50:36 Z finn__ Chorus (JOI23_chorus) C++17
0 / 100
 4 ms 8148 KB 
#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 = 1001;

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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8084 KB Output is correct
3 Correct 4 ms 8072 KB Output is correct
4 Incorrect 3 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8084 KB Output is correct
3 Correct 4 ms 8072 KB Output is correct
4 Incorrect 3 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8084 KB Output is correct
3 Correct 4 ms 8072 KB Output is correct
4 Incorrect 3 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8084 KB Output is correct
3 Correct 4 ms 8072 KB Output is correct
4 Incorrect 3 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8084 KB Output is correct
3 Correct 4 ms 8072 KB Output is correct
4 Incorrect 3 ms 8148 KB Output isn't correct
5 Halted 0 ms 0 KB -