oj.uz

Submission #934465

# Submission time Handle Problem Language Result Execution time Memory
934465 2024-02-27T11:03:42 Z boris_mihov Chorus (JOI23_chorus) C++17
40 / 100
 7000 ms 171988 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 5000 + 10;
const int INF  = 1e9;

int n, k;
int h[MAXN];
int next[MAXN];
int prev[MAXN];
llong prefix[MAXN];
llong dp[MAXN][MAXN];
bool bl[MAXN][MAXN];
char s[2 * MAXN];

llong cost(int l, int r)
{
    if (next[l] > r)
    {
        return 0;
    }

    return (next[l] - l + 1) * (l - 1) + prefix[r] - prefix[next[l]] - (r - l + 1) * (l - 1);
}

int f(int pos, int cnt)
{
    if (pos == n + 1)
    {
        if (cnt == k) return 0;
        return INF;
    }

    if (bl[pos][cnt])
    {
        return dp[pos][cnt];
    }

    dp[pos][cnt] = INF;
    bl[pos][cnt] = true;
    for (int next = pos + 1 ; next <= n + 1 ; ++next)
    {
        dp[pos][cnt] = std::min(dp[pos][cnt], f(next, cnt + 1) + cost(pos, next - 1));
    }

    return dp[pos][cnt];
}

void solve()
{
    int cntA = 0;
    int cntB = 0;
    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        if (s[i] == 'B')
        {
            cntB++;
        } else
        {
            cntA++;
            h[cntA] = cntB;
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + h[i];
    }

    next[n + 1] = n + 1;
    h[n + 1] = n + 1;
    for (int i = n ; i >= 1 ; --i)
    {
        next[i] = next[i + 1];
        while (next[i] >= i && h[next[i]] >= i)
        {
            next[i]--;
        }
    }

    prev[0] = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        prev[i] = prev[i - 1];
        while (prev[i] <= i && h[prev[i]] < i)
        {
            prev[i]++;
        }
    }

    std::cout << f(1, 0) << '\n';
}

void input()
{
    std::cin >> n >> k;
    std::cin >> s + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

chorus.cpp: In function 'void input()':
chorus.cpp:101:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |     std::cin >> s + 1;
      |                 ~~^~~

Subtask #1
16.0 / 16.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4560 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 8 ms 11244 KB Output is correct
18 Correct 119 ms 25136 KB Output is correct
19 Correct 120 ms 25176 KB Output is correct
20 Correct 119 ms 25412 KB Output is correct
21 Correct 133 ms 25176 KB Output is correct
22 Correct 128 ms 25144 KB Output is correct
23 Correct 129 ms 25408 KB Output is correct
24 Correct 116 ms 25440 KB Output is correct
25 Correct 117 ms 25204 KB Output is correct
26 Correct 120 ms 25180 KB Output is correct
27 Correct 118 ms 25176 KB Output is correct
28 Correct 143 ms 25124 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4560 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 8 ms 11244 KB Output is correct
18 Correct 119 ms 25136 KB Output is correct
19 Correct 120 ms 25176 KB Output is correct
20 Correct 119 ms 25412 KB Output is correct
21 Correct 133 ms 25176 KB Output is correct
22 Correct 128 ms 25144 KB Output is correct
23 Correct 129 ms 25408 KB Output is correct
24 Correct 116 ms 25440 KB Output is correct
25 Correct 117 ms 25204 KB Output is correct
26 Correct 120 ms 25180 KB Output is correct
27 Correct 118 ms 25176 KB Output is correct
28 Correct 143 ms 25124 KB Output is correct
29 Execution timed out 7011 ms 171988 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4560 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 8 ms 11244 KB Output is correct
18 Correct 119 ms 25136 KB Output is correct
19 Correct 120 ms 25176 KB Output is correct
20 Correct 119 ms 25412 KB Output is correct
21 Correct 133 ms 25176 KB Output is correct
22 Correct 128 ms 25144 KB Output is correct
23 Correct 129 ms 25408 KB Output is correct
24 Correct 116 ms 25440 KB Output is correct
25 Correct 117 ms 25204 KB Output is correct
26 Correct 120 ms 25180 KB Output is correct
27 Correct 118 ms 25176 KB Output is correct
28 Correct 143 ms 25124 KB Output is correct
29 Execution timed out 7011 ms 171988 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4560 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 8 ms 11244 KB Output is correct
18 Correct 119 ms 25136 KB Output is correct
19 Correct 120 ms 25176 KB Output is correct
20 Correct 119 ms 25412 KB Output is correct
21 Correct 133 ms 25176 KB Output is correct
22 Correct 128 ms 25144 KB Output is correct
23 Correct 129 ms 25408 KB Output is correct
24 Correct 116 ms 25440 KB Output is correct
25 Correct 117 ms 25204 KB Output is correct
26 Correct 120 ms 25180 KB Output is correct
27 Correct 118 ms 25176 KB Output is correct
28 Correct 143 ms 25124 KB Output is correct
29 Execution timed out 7011 ms 171988 KB Time limit exceeded
30 Halted 0 ms 0 KB -