oj.uz

Submission #850872

# Submission time Handle Problem Language Result Execution time Memory
850872 2023-09-17T15:20:20 Z danikoynov Chorus (JOI23_chorus) C++14
16 / 100
 4043 ms 511544 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 510;
int n, k;
string s;

int dp[maxn][maxn][maxn], pos[2][maxn];
/**

*/

void chmin(int &var, int val) /// careful for long long
{
    var = min(var, val);
}

void solve()
{
    cin >> n >> k >> s;

    s = "#" + s;
    int cntA = 0, cntB = 0;
    for (int i = 1; i <= 2 * n; i ++)
    {
        if (s[i] == 'A')
        {
            cntA ++;
            pos[0][cntA] = i;
        }
        else
        {
            cntB ++;
            pos[1][cntB] = i;
        }
    }

    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
        for (int k = 0; k <= n; k ++)
        dp[i][j][k] = 4 * n * n; /// careful for overflow

        int cr = 0;
    for (int j = 1; j <= n; j ++)
    {
        cr = cr + pos[0][j] - j;

        dp[1][j][j] = cr;
    }

    for (int i = 1; i < k; i ++)
    {
        for (int j = 1; j <= n; j ++)
            for (int k = 1; k <= j; k ++)
        {
            if (dp[i][j][k] == 4 * n * n)
                continue;
            /// i-th song, j open brackets, k - in the last one
            /// range [j * 2 - k + 1, j * 2]
            ///cout << "state " << i << " " << j << " " << k << " = " << dp[i][j][k] << endl;
            int tk = 0, atl = j * 2 - k + 1, atm = j * 2 + 1;
            for (int fix = 1; fix <= n - j; fix ++)
            {
                if (pos[0][fix + j] < atl)
                    tk += atl - pos[0][fix + j];
                else
                if (pos[0][fix + j] > atm)
                    tk += pos[0][fix + j] - atm;
            //cout << "transition " << fix << " " << tk << endl;
                ///cout << dp[i][j][k] + tk << " " << tk << endl;
                chmin(dp[i + 1][j + fix][fix], dp[i][j][k] + tk);
                atl ++;
                atm ++;
            }



        }
    }

    int ans = 4 * n * n;
    for (int j = 1; j <= n; j ++)
        ans = min(ans, dp[k][n][j]);
    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}

Compilation message

chorus.cpp: In function 'void solve()':
chorus.cpp:56:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |     for (int i = 0; i <= n; i ++)
      |     ^~~
chorus.cpp:61:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   61 |         int cr = 0;
      |         ^~~

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 1 ms 10584 KB Output is correct
17 Correct 82 ms 183208 KB Output is correct
18 Correct 2408 ms 511544 KB Output is correct
19 Incorrect 4043 ms 511536 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 1 ms 10584 KB Output is correct
17 Correct 82 ms 183208 KB Output is correct
18 Correct 2408 ms 511544 KB Output is correct
19 Incorrect 4043 ms 511536 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 1 ms 10584 KB Output is correct
17 Correct 82 ms 183208 KB Output is correct
18 Correct 2408 ms 511544 KB Output is correct
19 Incorrect 4043 ms 511536 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10584 KB Output is correct
14 Correct 2 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 1 ms 10584 KB Output is correct
17 Correct 82 ms 183208 KB Output is correct
18 Correct 2408 ms 511544 KB Output is correct
19 Incorrect 4043 ms 511536 KB Output isn't correct
20 Halted 0 ms 0 KB -