Submission #902686

#	Time	Username	Problem	Language	Result	Execution time	Memory
902686		Tuanlinh123	Chorus (JOI23_chorus)	C++17	87 / 100	7100 ms	661768 KiB

chorus

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
 
const long long inf=1e6, maxn=1e6+5;
long long cnt[maxn], to[maxn];
long long n, k, dp[maxn], pre[maxn];
 
struct Line
{
    long long a=inf, b=inf;
    ll idx=0;
 
    Line(){}
    Line(long long a, long long b, ll idx): a(a), b(b), idx(idx){}
    inline pair<long long, ll> ask(long long x)
    {
        if (a==inf) return {inf*inf, idx};
        return {a*x+b, idx};
    }
};
 
struct Node
{
    Line A;
    ll l=0, r=0;
};
Node LC[maxn*20];
 
struct Lichao
{
    ll crr;
    Lichao()
    {
        crr=0;
        LC[0]=Node();
    }
    inline void addline(Line A)
    {
        ll Start=0, End=inf, i=0;
        while (1)
        {
            ll mid=(Start+End)/2;
            bool l=A.ask(Start).fi<LC[i].A.ask(Start).fi;
            bool m=A.ask(mid).fi<LC[i].A.ask(mid).fi;
            if (m) swap(A, LC[i].A);
            if (A.a==inf) break;
            if (Start+1!=End)
            {
                if (l!=m)
                {
                    if (!LC[i].l)
                    {
                        LC[i].l=++crr;
                        LC[crr]=Node();
                    }
                    i=LC[i].l;
                    End=mid;
                }
                else
                {
                    if (!LC[i].r)
                    {
                        LC[i].r=++crr;
                        LC[crr]=Node();
                    }
                    i=LC[i].r;
                    Start=mid;
                }
            }
            else break;
        }
    }
 
    inline pair<long long, ll> query(long long x)
    {
        ll Start=0, End=inf, i=0;
        pair<long long, ll> ans={inf*inf, 0};
        while (1)
        {
            ll mid=(Start+End)/2;
            ans=min(ans, LC[i].A.ask(x));
            if (x<mid && LC[i].l)
            {
                i=LC[i].l;
                End=mid;
            }
            else if (x>=mid && LC[i].r)
            {
                i=LC[i].r;
                Start=mid;
            }
            else break;
        }
        return ans;
    }
};
 
pair<long long, ll> solve(long long C)
{
    ll crr=1;
    Lichao A; A.addline(Line(0, -pre[to[0]-1], 0));
    for (ll i=1; i<=n; i++)
        dp[i]=inf*inf, cnt[i]=0;
    for (ll i=1; i<=n; i++)
    {
        while (crr<i && to[crr]<=i)
            A.addline(Line(-crr, -(pre[to[crr]-1]-(to[crr]-1)*crr)+dp[crr], cnt[crr])), crr++;
        tie(dp[i], cnt[i])=A.query(i); 
        dp[i]+=C+pre[i], cnt[i]++;
        if (crr<i && dp[crr]+C<dp[i])
            dp[i]=dp[crr]+C, cnt[i]=cnt[crr]+1;
    }
    return {dp[n], cnt[n]};
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    string s; cin >> s;
    long long x=0, y=0, crr=1;
    for (ll i=0; i<n*2; i++)
    {
        if (s[i]=='A')
            x++, pre[x]=pre[x-1]+y;
        else y++;
    }
    for (ll i=1; i<=n; i++)
        while (crr<=pre[i]-pre[i-1])
            to[crr]=i, crr++;
    while (crr<=n) to[crr]=n+1, crr++;
    for (ll i=0; i<=n; i++)
        if (to[i]<=i)
            to[i]=i+1;
    long long lo=0, hi=1LL*n*n;
    while (hi>lo)
    {
        long long mid=(lo+hi)/2;
        if (solve(mid).se<=k)
            hi=mid;
        else lo=mid+1;
    }
    cout << 0LL+solve(lo).fi-lo*k;
}

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