Submission #902749

#	Time	Username	Problem	Language	Result	Execution time	Memory
902749		Tuanlinh123	Chorus (JOI23_chorus)	C++17	87 / 100	7098 ms	94352 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=LLONG_MAX, maxn=1e6+5;
long long cnt[maxn], to[maxn];
long long n, k, dp[maxn], pre[maxn];
 
struct Line
{
    mutable long long k, m, p, idx;
    bool operator < (const Line &o) const{return k<o.k;}
    bool operator < (long long o) const {return p<o;} 
};

struct CHT: multiset<Line, less<>>
{
    long long floordiv(long long a, long long b){return a/b-(((a^b)<0) && (a%b));}
    bool isect(iterator x, iterator y)
    {
        if (y==end())
        {
            x->p=inf;
            return false;
        }
        if (x->k==y->k) x->p=x->m>y->m ? inf:-inf;
        else x->p=floordiv(x->m-y->m, y->k-x->k);
        return x->p>=y->p;
    }
    void add(long long k, long long m, ll idx)
    {
        k = -k, m = -m;
        auto z=insert({k, m, 0, idx}), y=z++, x=y;
        while (isect(y, z)) z=erase(z);
        if (x!=begin() && isect(--x, y)) isect(x, y=erase(y));
        while ((y=x)!=begin() && ((--x)->p)>=y->p) isect(x, erase(y)); 
    }
    pair<long long, ll> query(ll x)
    {
        auto L=*lower_bound(x);
        return {-L.k*x-L.m, L.idx};
    }
};
 
pair<long long, ll> solve(long long C)
{
    ll crr=1;
    CHT A; A.add(0, -pre[to[0]-1], 0);
    for (ll i=1; i<=n; i++)
        dp[i]=inf, cnt[i]=0;
    for (ll i=1; i<=n; i++)
    {
        while (crr<i && to[crr]<=i)
            A.add(-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