Submission #901744

#	Time	Username	Problem	Language	Result	Execution time	Memory
901744		Tuanlinh123	Chorus (JOI23_chorus)	C++17	87 / 100	7059 ms	856352 KiB

chorus

#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=2e9, maxn=1e6+5;
long long n, k, to[maxn];
long long 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){}
    pair<long long, ll> ask(ll x)
    {
        if (a==inf) return {inf*inf, idx};
        return {a*x+b, idx};
    }
};

struct Node
{
    Line A;
    Node *l, *r;
};

struct Lichao
{
    Node *root=new Node();
    void addline(Line A)
    {
        ll Start=-inf, End=inf;
        Node *i=root;
        while (1)
        {
            if (A.a==inf) break;
            ll mid=(Start+End)/2;
            bool l=A.ask(Start).fi<i->A.ask(Start).fi;
            bool m=A.ask(mid).fi<i->A.ask(mid).fi;
            if (m) swap(A, i->A);
            if (Start+1!=End)
            {
                if (l!=m)
                {
                    if (!i->l)
                        i->l=new Node();
                    i=i->l;
                    End=mid;
                }
                else
                {
                    if (!i->r)
                        i->r=new Node();
                    i=i->r;
                    Start=mid;
                }
            }
            else break;
        }
    }

    pair<long long, ll> query(ll x)
    {
        Node *i=root;
        ll Start=-inf, End=inf;
        pair<long long, ll> ans={inf*inf, 0};
        while (1)
        {
            ll mid=(Start+End)/2;
            ans=min(ans, i->A.ask(x));
            if (x<mid && i->l)
            {
                i=i->l;
                End=mid;
            }
            else if (x>=mid && i->r)
            {
                i=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));
    vector <long long> dp(n+1, inf*inf); dp[0]=0;
    vector <ll> cnt(n+1, 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;
        // cout << i << " " << dp[i] << " " << cnt[i] << "\n";
    }
    // cout << C << " " << dp[n] << " " << cnt[n] << "\n";
    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;
    ll 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-k*lo;
}

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