Submission #796353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796353	2023-07-28T10:15:27 Z	finn__	Chorus (JOI23_chorus)	C++17	16 / 100	2 ms	2260 KB

chorus

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

constexpr size_t N = 501;

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2260 KB	Output is correct
2	Correct	1 ms	2260 KB	Output is correct
3	Correct	1 ms	2260 KB	Output is correct
4	Correct	1 ms	2260 KB	Output is correct
5	Correct	1 ms	2260 KB	Output is correct
6	Correct	1 ms	2244 KB	Output is correct
7	Correct	1 ms	2260 KB	Output is correct
8	Correct	1 ms	2260 KB	Output is correct
9	Correct	2 ms	2260 KB	Output is correct
10	Correct	1 ms	2260 KB	Output is correct
11	Correct	1 ms	2260 KB	Output is correct
12	Correct	1 ms	2260 KB	Output is correct
13	Correct	1 ms	2244 KB	Output is correct
14	Correct	1 ms	2260 KB	Output is correct
15	Correct	1 ms	2260 KB	Output is correct
16	Correct	1 ms	2260 KB	Output is correct

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2260 KB	Output is correct
2	Correct	1 ms	2260 KB	Output is correct
3	Correct	1 ms	2260 KB	Output is correct
4	Correct	1 ms	2260 KB	Output is correct
5	Correct	1 ms	2260 KB	Output is correct
6	Correct	1 ms	2244 KB	Output is correct
7	Correct	1 ms	2260 KB	Output is correct
8	Correct	1 ms	2260 KB	Output is correct
9	Correct	2 ms	2260 KB	Output is correct
10	Correct	1 ms	2260 KB	Output is correct
11	Correct	1 ms	2260 KB	Output is correct
12	Correct	1 ms	2260 KB	Output is correct
13	Correct	1 ms	2244 KB	Output is correct
14	Correct	1 ms	2260 KB	Output is correct
15	Correct	1 ms	2260 KB	Output is correct
16	Correct	1 ms	2260 KB	Output is correct
17	Incorrect	2 ms	2196 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2260 KB	Output is correct
2	Correct	1 ms	2260 KB	Output is correct
3	Correct	1 ms	2260 KB	Output is correct
4	Correct	1 ms	2260 KB	Output is correct
5	Correct	1 ms	2260 KB	Output is correct
6	Correct	1 ms	2244 KB	Output is correct
7	Correct	1 ms	2260 KB	Output is correct
8	Correct	1 ms	2260 KB	Output is correct
9	Correct	2 ms	2260 KB	Output is correct
10	Correct	1 ms	2260 KB	Output is correct
11	Correct	1 ms	2260 KB	Output is correct
12	Correct	1 ms	2260 KB	Output is correct
13	Correct	1 ms	2244 KB	Output is correct
14	Correct	1 ms	2260 KB	Output is correct
15	Correct	1 ms	2260 KB	Output is correct
16	Correct	1 ms	2260 KB	Output is correct
17	Incorrect	2 ms	2196 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2260 KB	Output is correct
2	Correct	1 ms	2260 KB	Output is correct
3	Correct	1 ms	2260 KB	Output is correct
4	Correct	1 ms	2260 KB	Output is correct
5	Correct	1 ms	2260 KB	Output is correct
6	Correct	1 ms	2244 KB	Output is correct
7	Correct	1 ms	2260 KB	Output is correct
8	Correct	1 ms	2260 KB	Output is correct
9	Correct	2 ms	2260 KB	Output is correct
10	Correct	1 ms	2260 KB	Output is correct
11	Correct	1 ms	2260 KB	Output is correct
12	Correct	1 ms	2260 KB	Output is correct
13	Correct	1 ms	2244 KB	Output is correct
14	Correct	1 ms	2260 KB	Output is correct
15	Correct	1 ms	2260 KB	Output is correct
16	Correct	1 ms	2260 KB	Output is correct
17	Incorrect	2 ms	2196 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2260 KB	Output is correct
2	Correct	1 ms	2260 KB	Output is correct
3	Correct	1 ms	2260 KB	Output is correct
4	Correct	1 ms	2260 KB	Output is correct
5	Correct	1 ms	2260 KB	Output is correct
6	Correct	1 ms	2244 KB	Output is correct
7	Correct	1 ms	2260 KB	Output is correct
8	Correct	1 ms	2260 KB	Output is correct
9	Correct	2 ms	2260 KB	Output is correct
10	Correct	1 ms	2260 KB	Output is correct
11	Correct	1 ms	2260 KB	Output is correct
12	Correct	1 ms	2260 KB	Output is correct
13	Correct	1 ms	2244 KB	Output is correct
14	Correct	1 ms	2260 KB	Output is correct
15	Correct	1 ms	2260 KB	Output is correct
16	Correct	1 ms	2260 KB	Output is correct
17	Incorrect	2 ms	2196 KB	Output isn't correct
18	Halted	0 ms	0 KB	-