제출 #938528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938528		Ice_man	Chorus (JOI23_chorus)	C++14	40 / 100	3349 ms	498480 KiB

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 / 16
• Subtask 2: 24 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13