Submission #804746

#	Time	Username	Problem	Language	Result	Execution time	Memory
804746		mousebeaver	Chorus (JOI23_chorus)	C++14	16 / 100	7040 ms	2260 KiB

chorus

#define ll long long
#define INF numeric_limits<ll>::max()/2
#include <bits/stdc++.h>
using namespace std;

ll sum(ll l, ll r, vector<ll>& pref)
{
    return pref[r] - (l == 0 ? 0 : pref[l-1]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, k;
    cin>>n>>k;
    string s;
    cin>>s;
    vector<ll> a(0);
    for(ll i = 0; i < 2*n; i++)
    {
        if(s[i] == 'A')
        {
            a.push_back(i+1);
        }
    }
    ll output = 0;
    for(ll i = 0; i < n; i++)
    {
        if(a[i] > 2*i+1)
        {
            output += a[i] - (2*i+1);
            a[i] = 2*i+1;
        }
    }
    vector<ll> pref(n);
    pref[0] = a[0];
    for(ll i = 1; i < n; i++)
    {
        pref[i] = a[i];
    }

    vector<vector<ll>> dp(n+1, vector<ll> (k+1, INF)); //n x 'A', k songs => Min operations
    dp[0][0] = 0;
    for(ll i = 1; i <= n; i++)
    {
        for(ll j = 1; j <= k; j++)
        {
            for(ll c = 0; c < i; c++)
            {
                ll cost = 0;
                ll goal = 2*c+1;
                for(ll d = c; d < i; d++)
                {
                    if(a[d] > goal)
                    {
                        cost += a[d]-goal;
                    }
                    goal++;
                }
                dp[i][j] = min(dp[i][j], dp[c][j-1]+cost);                
            }
        }
    }

    ll res = *min_element(dp[n].begin(), dp[n].end());
    cout<<res+output<<"\n";

    return 0;  
}

/*ll test(string& s)
{
    ll n = s.length();
    ll counter = 0;
    for(ll i = 0; i < n; i++)
    {
        counter += (s[i] == 'A' ? 1 : -1);
        if(counter < 0)
        {
            return INF;
        }
    }

    ll a = 0;
    while(s[a] == 'B')
    {
        a++;
    }
    ll b = 0;
    while(s[b] == 'A')
    {
        b++;
    }

    ll output = 0;
    while(b < n)
    {
        output++;
        counter = 0;
        while(a < b)
        {
            counter += (s[a] == 'A');
            a++;
        }
        while(counter > 0)
        {
            counter -= (s[b] == 'B');
            b++;
        }
        while(s[b] == 'A')
        {
            b++;
        }
    }

    return output;   
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, k;
    cin>>n>>k;
    ll counter = 0; 
    string s;
    cin>>s;

    ll index = 2*n-1;
    while(test(s) > k)
    {
        counter++;
        while(s[index] == 'A' || (index == 2*n-1 || s[index+1] == 'B'))
        {
            index--;
        }
        swap(s[index], s[index+1]);
        index++;
    }
    cout<<counter<<"\n";

    return 0;
}*/

• Subtask 1: 16 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13