답안 #938528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938528	2024-03-05T08:59:48 Z	Ice_man	Chorus (JOI23_chorus)	C++14	40 / 100	3349 ms	498480 KB

chorus

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #938528

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0