oj.uz

Submission #938528

# Submission time Handle Problem Language Result Execution time Memory
938528 2024-03-05T08:59:48 Z Ice_man Chorus (JOI23_chorus) C++14
40 / 100
 3349 ms 498480 KB 
#include <iostream>
#include <chrono>

#define maxn 5005
#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;
}


long long n, k;
string s;

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

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


long long pref[2][maxn][maxn];
long long pom[maxn];


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


    for(long long i = 0; i < n / 2 + 1; i++)
        for(long long j = 1; j <= n; j++)
        {
            pref[0][i][j] = pref[1][i][j] = max(0LL , 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];
        }
}



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

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

    long long ret = 0;
    long long len = r - l + 1;
    long long 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;

    /**long long ret = 0;

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

    return ret;*/
}


long long dp2[maxn][maxn];

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

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

    ///cout << pos << endl;

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

    for(long long 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;
        }

    long long mid = pos / 2;

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

long long ans = INF;

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

    for(long long 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(long long i = 0; i < 2 * n; i++)
        cout << a[i] << " ";
    cout << endl;

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

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

dp[0][0] = 0;

for(long long i = 1; i <= k; i++)
    for(long long j = 1; j <= n; j++)
        for(long long _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 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 4580 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 4580 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 15 ms 47960 KB Output is correct
18 Correct 38 ms 124164 KB Output is correct
19 Correct 23 ms 123976 KB Output is correct
20 Correct 15 ms 124248 KB Output is correct
21 Correct 14 ms 123992 KB Output is correct
22 Correct 28 ms 123996 KB Output is correct
23 Correct 28 ms 123996 KB Output is correct
24 Correct 15 ms 123996 KB Output is correct
25 Correct 28 ms 123996 KB Output is correct
26 Correct 25 ms 123992 KB Output is correct
27 Correct 19 ms 121948 KB Output is correct
28 Correct 19 ms 121948 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 4580 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 15 ms 47960 KB Output is correct
18 Correct 38 ms 124164 KB Output is correct
19 Correct 23 ms 123976 KB Output is correct
20 Correct 15 ms 124248 KB Output is correct
21 Correct 14 ms 123992 KB Output is correct
22 Correct 28 ms 123996 KB Output is correct
23 Correct 28 ms 123996 KB Output is correct
24 Correct 15 ms 123996 KB Output is correct
25 Correct 28 ms 123996 KB Output is correct
26 Correct 25 ms 123992 KB Output is correct
27 Correct 19 ms 121948 KB Output is correct
28 Correct 19 ms 121948 KB Output is correct
29 Incorrect 3349 ms 498480 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 4580 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 15 ms 47960 KB Output is correct
18 Correct 38 ms 124164 KB Output is correct
19 Correct 23 ms 123976 KB Output is correct
20 Correct 15 ms 124248 KB Output is correct
21 Correct 14 ms 123992 KB Output is correct
22 Correct 28 ms 123996 KB Output is correct
23 Correct 28 ms 123996 KB Output is correct
24 Correct 15 ms 123996 KB Output is correct
25 Correct 28 ms 123996 KB Output is correct
26 Correct 25 ms 123992 KB Output is correct
27 Correct 19 ms 121948 KB Output is correct
28 Correct 19 ms 121948 KB Output is correct
29 Incorrect 3349 ms 498480 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 6492 KB Output is correct
5 Correct 1 ms 4580 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 15 ms 47960 KB Output is correct
18 Correct 38 ms 124164 KB Output is correct
19 Correct 23 ms 123976 KB Output is correct
20 Correct 15 ms 124248 KB Output is correct
21 Correct 14 ms 123992 KB Output is correct
22 Correct 28 ms 123996 KB Output is correct
23 Correct 28 ms 123996 KB Output is correct
24 Correct 15 ms 123996 KB Output is correct
25 Correct 28 ms 123996 KB Output is correct
26 Correct 25 ms 123992 KB Output is correct
27 Correct 19 ms 121948 KB Output is correct
28 Correct 19 ms 121948 KB Output is correct
29 Incorrect 3349 ms 498480 KB Output isn't correct
30 Halted 0 ms 0 KB -