oj.uz

Submission #938531

# Submission time Handle Problem Language Result Execution time Memory
938531 2024-03-05T09:01:42 Z Ice_man Chorus (JOI23_chorus) C++14
61 / 100
 3913 ms 783836 KB 
#include <iostream>
#include <chrono>

#define maxn 10001
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


int n, k;
string s;

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

    n *= 2;
    s = ' ' + s;
}


int pref[2][maxn][maxn];
int pom[maxn];


void math()
{
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'A')
            pom[i] = 1;
        else
            pom[i] = -1;
        pom[i] += pom[i - 1];
    }


    for(int i = 0; i < n / 2 + 1; i++)
        for(int j = 1; j <= n; j++)
        {
            pref[0][i][j] = pref[1][i][j] = max(0 , i - pom[j]);

            if(i == 0)
                continue;

            pref[0][i][j] += pref[0][i - 1][j - 1];
            pref[1][i][j] += pref[1][i - 1][j + 1];
        }
}



int dp[maxn][maxn], a[maxn];
int bra, brb;

int calc(int l, int r)
{
    if((r - l + 1) % 2 == 1)
        return INF;

    int ret = 0;
    int len = r - l + 1;
    int mid = (l + r) / 2;

    ret += pref[0][len / 2][mid];
    ret -= pref[0][0][mid - len / 2];
    ret += pref[1][len / 2 - 1][mid + 1];
    ret /= 2;

    return ret;

    /**int ret = 0;

    for(int i = y + 1; i <= x; i++)
        if(a[i] >= y)
            ret += a[i] - y;

    return ret;*/
}


int dp2[maxn][maxn];

void divide(int ansl, int ansr, int l, int r, int son)
{
    if(l > r)
        return;

    int pos = l + r;
    if((l + r) % 2 == 1)
        pos--;

    ///cout << pos << endl;

    dp2[pos][son] = ansr;
    dp[pos][son] = INF;

    for(int i = min(ansr , pos); i >= ansl; i--)
        if(dp[pos][son] > dp[i - 1][son - 1] + calc(i, pos))
        {
            dp[pos][son] = dp[i - 1][son - 1] + calc(i, pos);
            dp2[pos][son] = i;
        }

    int mid = pos / 2;

    divide(ansl, dp2[pos][son], l, mid - 1, son);
    divide(dp2[pos][son], ansr, mid + 1, r, son);
}

int ans = INF;

void solve()
{
    ans = INF;
    for(int i = 1; i <= n; i++)
        dp[i][0] = INF;

    for(int i = 1; i <= k; i++)
    {
        divide(1, n, 1, n / 2, i);
        ans = min(ans, dp[n][i]);
    }

    cout << ans << endl;
}



/**void calc_dp()
{
    bra = 0;
    brb = 0;

    for(char c : s)
        if(c == 'A')
        {
            bra++;
            a[bra] = brb;
        }
        else
            brb++;
*/
    /**for(int i = 0; i < 2 * n; i++)
        cout << a[i] << " ";
    cout << endl;

    cout << bra << " " << brb << endl;*/

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

dp[0][0] = 0;

for(int i = 1; i <= k; i++)
    for(int j = 1; j <= n; j++)
        for(int _k = 0; _k < j; _k++)
        {
            ///cout << calc(_k , j) << endl;
            dp[i][j] = min(dp[i][j] , dp[i - 1][_k] + calc(_k , j));
        }


cout << dp[k][n] << endl;
}*/




int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();
    math();
    solve();


    return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8712 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 1 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 12 ms 45656 KB Output is correct
18 Correct 37 ms 121680 KB Output is correct
19 Correct 21 ms 121692 KB Output is correct
20 Correct 13 ms 121692 KB Output is correct
21 Correct 14 ms 121688 KB Output is correct
22 Correct 28 ms 121540 KB Output is correct
23 Correct 27 ms 121564 KB Output is correct
24 Correct 14 ms 121692 KB Output is correct
25 Correct 30 ms 121772 KB Output is correct
26 Correct 27 ms 122100 KB Output is correct
27 Correct 19 ms 121688 KB Output is correct
28 Correct 19 ms 121692 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8712 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 1 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 12 ms 45656 KB Output is correct
18 Correct 37 ms 121680 KB Output is correct
19 Correct 21 ms 121692 KB Output is correct
20 Correct 13 ms 121692 KB Output is correct
21 Correct 14 ms 121688 KB Output is correct
22 Correct 28 ms 121540 KB Output is correct
23 Correct 27 ms 121564 KB Output is correct
24 Correct 14 ms 121692 KB Output is correct
25 Correct 30 ms 121772 KB Output is correct
26 Correct 27 ms 122100 KB Output is correct
27 Correct 19 ms 121688 KB Output is correct
28 Correct 19 ms 121692 KB Output is correct
29 Correct 1828 ms 525356 KB Output is correct
30 Correct 3329 ms 623212 KB Output is correct
31 Correct 893 ms 494240 KB Output is correct
32 Correct 108 ms 454068 KB Output is correct
33 Correct 115 ms 453984 KB Output is correct
34 Correct 3803 ms 649156 KB Output is correct
35 Correct 3760 ms 649388 KB Output is correct
36 Correct 132 ms 454480 KB Output is correct
37 Correct 952 ms 493140 KB Output is correct
38 Correct 3244 ms 615664 KB Output is correct
39 Correct 2093 ms 547008 KB Output is correct
40 Correct 1634 ms 519008 KB Output is correct
41 Correct 1570 ms 519004 KB Output is correct
42 Correct 3913 ms 519140 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8712 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 1 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 12 ms 45656 KB Output is correct
18 Correct 37 ms 121680 KB Output is correct
19 Correct 21 ms 121692 KB Output is correct
20 Correct 13 ms 121692 KB Output is correct
21 Correct 14 ms 121688 KB Output is correct
22 Correct 28 ms 121540 KB Output is correct
23 Correct 27 ms 121564 KB Output is correct
24 Correct 14 ms 121692 KB Output is correct
25 Correct 30 ms 121772 KB Output is correct
26 Correct 27 ms 122100 KB Output is correct
27 Correct 19 ms 121688 KB Output is correct
28 Correct 19 ms 121692 KB Output is correct
29 Correct 1828 ms 525356 KB Output is correct
30 Correct 3329 ms 623212 KB Output is correct
31 Correct 893 ms 494240 KB Output is correct
32 Correct 108 ms 454068 KB Output is correct
33 Correct 115 ms 453984 KB Output is correct
34 Correct 3803 ms 649156 KB Output is correct
35 Correct 3760 ms 649388 KB Output is correct
36 Correct 132 ms 454480 KB Output is correct
37 Correct 952 ms 493140 KB Output is correct
38 Correct 3244 ms 615664 KB Output is correct
39 Correct 2093 ms 547008 KB Output is correct
40 Correct 1634 ms 519008 KB Output is correct
41 Correct 1570 ms 519004 KB Output is correct
42 Correct 3913 ms 519140 KB Output is correct
43 Runtime error 963 ms 783836 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8712 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 1 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 12 ms 45656 KB Output is correct
18 Correct 37 ms 121680 KB Output is correct
19 Correct 21 ms 121692 KB Output is correct
20 Correct 13 ms 121692 KB Output is correct
21 Correct 14 ms 121688 KB Output is correct
22 Correct 28 ms 121540 KB Output is correct
23 Correct 27 ms 121564 KB Output is correct
24 Correct 14 ms 121692 KB Output is correct
25 Correct 30 ms 121772 KB Output is correct
26 Correct 27 ms 122100 KB Output is correct
27 Correct 19 ms 121688 KB Output is correct
28 Correct 19 ms 121692 KB Output is correct
29 Correct 1828 ms 525356 KB Output is correct
30 Correct 3329 ms 623212 KB Output is correct
31 Correct 893 ms 494240 KB Output is correct
32 Correct 108 ms 454068 KB Output is correct
33 Correct 115 ms 453984 KB Output is correct
34 Correct 3803 ms 649156 KB Output is correct
35 Correct 3760 ms 649388 KB Output is correct
36 Correct 132 ms 454480 KB Output is correct
37 Correct 952 ms 493140 KB Output is correct
38 Correct 3244 ms 615664 KB Output is correct
39 Correct 2093 ms 547008 KB Output is correct
40 Correct 1634 ms 519008 KB Output is correct
41 Correct 1570 ms 519004 KB Output is correct
42 Correct 3913 ms 519140 KB Output is correct
43 Runtime error 963 ms 783836 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -