제출 #804799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804799		mousebeaver	Chorus (JOI23_chorus)	C++14	40 / 100	7007 ms	79488 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 = 0; i < n; i++)
    {
        for(ll j = 0; j < k; j++)
        {
            ll goal = 2*i+1;
            ll cost = 0;
            for(ll c = i+1; c <= n; c++)
            {
                if(a[c-1] > goal)
                {
                    cost += a[c-1]-goal;
                }
                goal++;
                dp[c][j+1] = min(dp[c][j+1], dp[i][j]+cost);
            }
        }
    }
    /*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;  
}

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