oj.uz

Submission #796356

# Submission time Handle Problem Language Result Execution time Memory
796356 2023-07-28T10:16:53 Z finn__ Chorus (JOI23_chorus) C++17
16 / 100
 4 ms 8148 KB 
#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.0 / 16.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 13.0

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