Submission #902733

#	Time	Username	Problem	Language	Result	Execution time	Memory
902733		Tuanlinh123	Chorus (JOI23_chorus)	C++17	87 / 100	7053 ms	83560 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 Lichao
{
    struct node
    {
        ll l=-1, r=-1;
        pair<pair<long long, long long>, ll> line;
        node(long long a, long long b, int idx): line({a, b}, idx){}
        pair<long long, ll> eval(ll x){return {line.fi.fi*x+line.fi.se, line.se};}
    };

    const ll MAXV=1'000'000;
    vector<node> tree;

    void insert(long long a, long long b, ll idx)
    {
        node c(a, b, idx);
        if (tree.empty())
        {
            tree.push_back(c);
            return;
        }
        ll tidx=0, Start=-MAXV, End=MAXV;
        while (Start<=End)
        {
            ll mid=(Start+End)/2;
            bool s=c.eval(Start).fi<tree[tidx].eval(Start).fi;
            bool m=c.eval(mid).fi<tree[tidx].eval(mid).fi;
            if (m) swap(c.line, tree[tidx].line);
            if (Start==End) return;
            if (s!=m)
            {
                End=mid-1;
                if (tree[tidx].l==-1)
                {
                    tree[tidx].l=tree.size();
                    tree.push_back(c);
                    return;
                }
                tidx=tree[tidx].l;
            }
            else
            {
                Start=mid+1;
                if (tree[tidx].r==-1)
                {
                    tree[tidx].r=tree.size();
                    tree.push_back(c);
                    return;
                }
                tidx=tree[tidx].r;
            }
        }
    }

    pair<long long, ll> query(ll x)
    {
        pair<long long, ll> ans={LLONG_MAX, 0};
        ll tidx = 0, Start = -MAXV, End = MAXV;
        while (Start<=End && tidx!=-1)
        {
            ans=min(ans, tree[tidx].eval(x));
            ll mid=(Start+End)/2;
            if (x==mid) return ans;
            if (x<mid) End=mid-1, tidx=tree[tidx].l;
            else Start=mid+1, tidx=tree[tidx].r;
        }
        return ans;
    }
};
 
pair<long long, ll> solve(long long C)
{
    ll crr=1;
    Lichao A; A.insert(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.insert(-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