Submission #902769

#	Time	Username	Problem	Language	Result	Execution time	Memory
902769		Tuanlinh123	Chorus (JOI23_chorus)	C++17	100 / 100	3047 ms	86620 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
{
    int csz = 0;
    vector <Line> data;
    long long floordiv(long long a, long long b){return a/b-(((a^b)<0) && (a%b));}
    long long isect(Line x, Line y) {
        if (x.k == y.k) return (x.m > y.m ? inf : -inf);
        return floordiv(x.m - y.m, y.k - x.k);
    }
    void add(long long k, long long m, ll idx)
    {
        k = -k, m = -m;
        Line L = {k, m, inf, idx};
        while (csz >= 2 and isect(data[csz - 2], data[csz - 1]) >= isect(data[csz - 1], L)) {
            --csz; data.pop_back();
            if (csz >= 2) data[csz - 2].p = isect(data[csz - 2], data[csz - 1]);
        }
        if (csz) data.back().p = isect(data.back(), L);
        ++csz; data.push_back(L);
    }
    pair<long long, ll> query(ll x)
    {
        auto L = *lower_bound(data.begin(), data.end(), 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);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    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: 13 / 13