Submission #925097

#	Time	Username	Problem	Language	Result	Execution time	Memory
925097		ttamx	Chorus (JOI23_chorus)	C++14	0 / 100	2 ms	4444 KiB

chorus

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;

const int N=1e6+5;

int n,k;
string s;
int a[N],b[N];
ll qs[N];
pl dp[N];

struct Line{
    ll m,c,cnt;
    Line(ll _m,ll _c,ll _cnt):m(_m),c(_c),cnt(_cnt){}
    ll eval(ll x){
        return m*x+c;
    }
};

struct CHT{
    deque<Line> hull;
    bool bad(Line x,Line y,Line z){
        return (y.c-x.c)*(z.m-x.m)>(x.c-z.c)*(y.m-x.m);
    }
    void insert(ll m,ll c,ll cnt){
        Line v(m,c,cnt);
        while(hull.size()>1&&bad(hull.end()[-2],hull.back(),v))hull.pop_back();
        hull.emplace_back(v);
    }
    pl query(ll x){
        while(hull.size()>1&&hull[0].eval(x)>hull[1].eval(x))hull.pop_front();
        return pl(hull[0].eval(x),hull[0].cnt);
    }
};

pl solve(ll lambda){
    CHT cht;
    cht.insert(0,1e18,0);
    deque<int> dq;
    for(int i=1;i<=n;i++){
        while(!dq.empty()&&b[dq.front()]<i){
            int j=dq.front();
            dq.pop_front();
            cht.insert(-j,dp[j].first-qs[b[j]]+1LL*j*b[j],dp[j].second);
        }
        dp[i]=cht.query(i);
        dp[i].first+=qs[i];
        dp[i]=min(dp[i],pl(qs[i],0));
        if(!dq.empty())dp[i]=min(dp[i],dp[dq.front()]);
        dp[i].first+=lambda;
        dp[i].second++;
        while(!dq.empty()&&dp[dq.back()]>dp[i])dq.pop_back();
        dq.emplace_back(i);
    }
    return dp[n];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> s;
    for(int i=0,ia=0,ib=0;i<2*n;i++){
        if(s[i]=='A'){
            a[++ia]=ib;
        }else{
            ib++;
            b[ib]=max(ib,ia);
        }
    }
    for(int i=1;i<=n;i++)qs[i]=qs[i-1]+a[i];
    ll l=0,r=1LL*n*n,ans;
    while(l<=r){
        ll m=(l+r)/2;
        auto [val,cnt]=solve(m);
        if(cnt>=k)ans=val-m*k,l=m+1;
        else r=m-1;
    }
    cout << ans;
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         auto [val,cnt]=solve(m);
      |              ^

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