제출 #796356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796356		finn__	Chorus (JOI23_chorus)	C++17	16 / 100	4 ms	8148 KiB

chorus

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

constexpr size_t N = 1001;

size_t f[N][N], min_b[N], a_sum[N], num_a[N];

size_t preprocess(string &s)
{
    size_t n = s.size(), p = 0, operations = 0;
    for (size_t i = 0; i < n; ++i)
    {
        if (s[i] == 'A')
        {
            ++p;
        }
        else
        {
            if (!p)
            {
                for (size_t j = i + 1; j < n; ++j)
                    if (s[j] == 'A')
                    {
                        assert(copy_backward(s.begin() + i, s.begin() + j, s.begin() + j + 1) == s.begin() + i + 1);
                        s[i] = 'A';
                        operations += j - i;
                        break;
                    }
                ++p;
            }
            else
            {
                --p;
            }
        }
    }

    return operations;
}

size_t get_a_sum(size_t i, size_t j)
{
    if (i > j)
        return 0;
    return a_sum[j] - (i ? a_sum[i - 1] : 0);
}

size_t get_num_a(size_t i, size_t j)
{
    if (i > j)
        return 0;
    return num_a[j] - (i ? num_a[i - 1] : 0);
}

size_t gauss(size_t n)
{
    return (n * (n + 1)) / 2;
}

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

    size_t n, k;
    string s;
    cin >> n >> k >> s;
    size_t ans = preprocess(s);

    size_t i = 0, j = 0, num_groups = 0;
    while (j < n << 1)
    {
        while (j < n << 1 && s[j] == 'A')
            ++j;
        min_b[num_groups] = j;
        size_t group_size = 0;
        while (i < j)
        {
            if (s[i] == 'A')
            {
                ++group_size;
                a_sum[num_groups] += i;
                num_a[num_groups]++;
            }
            ++i;
        }

        while (group_size--)
        {
            ++j;
            while (j < n << 1 && s[j] == 'A')
                ++j;
        }

        ++num_groups;
    }

    for (size_t i = 1; i < num_groups; ++i)
        a_sum[i] += a_sum[i - 1], num_a[i] += num_a[i - 1];

    memset(f, 255, sizeof f);
    f[0][0] = 0;
    for (size_t i = 0; i < num_groups; ++i)
        for (size_t j = 0; j <= i && j < k; ++j)
            if (f[i][j] != SIZE_MAX)
                for (size_t h = i + 1; h <= num_groups; ++h)
                {
                    // we merge all groups in i..h
                    size_t x = get_a_sum(i + 1, h - 1), y = get_num_a(i + 1, h - 1);
                    f[h][j + 1] = min(f[h][j + 1], f[i][j] + x - min_b[i] * y - gauss(y - 1));
                }

    cout << ans + f[num_groups][k] << '\n';
}

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