Submission #901548

#	Time	Username	Problem	Language	Result	Execution time	Memory
901548		Tuanlinh123	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	348 KiB

chorus

#include<bits/stdc++.h>
#define ll long long
#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 ll inf=2e9, maxn=1e6;
ll pre[maxn], to[maxn];
ll n, k;

struct Line
{
    ll a=inf, b=inf, idx;

    Line(){}
    Line(ll idx): idx(idx){}
    Line(ll a, ll b): a(a), b(b){}
    pll ask(ll x)
    {
        if (a==inf) return {inf*inf, idx};
        return {a*x+b, idx};
    }
};

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

    Node(){}
    Node(ll idx): A(Line(idx)){}
};
Node *root=new Node();

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

    pll query(ll x)
    {
        Node *i=root;
        ll Start=-inf, End=inf;
        pll 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;
    }
};

ll cost(ll j, ll i)
{
    if (to[j]>i) return 0;
    return (pre[i]-i*j)-(pre[to[j]-1]-(to[j]-1)*j);
}

pll solve(ll C)
{
    vector <ll> dp(n+1, inf*inf), cnt(n+1, 0);
    dp[0]=0;
    for (ll i=1; i<=n; i++)
        for (ll j=0; j<i; j++)
            if (dp[j]+cost(j, i)+C<dp[i])
                dp[i]=dp[j]+cost(j, i)+C, cnt[i]=cnt[j]+1;
    return {dp[n]-cnt[n]*C, 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++;
    }
    to[0]=1;
    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++;
    ll lo=0, hi=n*n;
    while (hi>lo)
    {
        ll mid=(lo+hi)/2;
        if (solve(mid).se<=k)
            hi=mid;
        else lo=mid+1;
    }
    cout << solve(lo).fi;
}

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