Submission #1242932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242932		Hanksburger	Chorus (JOI23_chorus)	C++20	100 / 100	1374 ms	55640 KiB

chorus

#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int, int> dp[1000005];
vector<int> a, b, sum;
int calc(pair<int, int> line, int x)
{
    return line.first*x+line.second;
}
long double intersect(pair<int, int> line1, pair<int, int> line2)
{
    return (long double)(line1.second-line2.second)/(line2.first-line1.first);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, cnt=0, ans=0;
    string s, str;
    cin >> n >> k >> s;
    for (int i=0; i<n*2; i++)
    {
        if (s[i]=='A' && cnt<0)
            ans-=cnt;
        if (s[i]=='A')
            cnt++;
        else
            cnt--;
        if (cnt<=0)
            str.push_back('A'+(int)(i&1));
        else
            str.push_back(s[i]);
    }
    for (int i=0; i<n*2; i++)
    {
        if (str[i]=='A')
            a.push_back(i);
        else
            b.push_back(i);
    }
    sum.push_back(a[0]);
    for (int i=1; i<n; i++)
        sum.push_back(sum.back()+a[i]-i);
    int l=0, r=n*n;
    while (1)
    {
        int C=(l+r)/2;
        deque<pair<pair<int, int>, int> > q;
        q.push_back({{0, 0}, 0});
        for (int i=1; i<=n; i++)
        {
            while (q.size()>=2 && calc(q[0].first, i)>calc(q[1].first, i))
                q.pop_front();
            dp[i]={calc(q[0].first, i)+sum[i-1]+C, q[0].second+1};
            pair<int, int> p={-i, dp[i].first+i*(b[i-1]-(i-1))-sum[b[i-1]-i]};
            while (q.size()>=2 && intersect(q[q.size()-1].first, p)<intersect(q[q.size()-2].first, q[q.size()-1].first))
                q.pop_back();
            q.push_back({p, dp[i].second});
        }
        if (l==r)
            break;
        if (dp[n].second>k)
            l=C+1;
        else
            r=C;
    }
    cout << ans+dp[n].first-l*k;
}

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