Submission #834718

#	Time	Username	Problem	Language	Result	Execution time	Memory
834718		alvingogo	Chorus (JOI23_chorus)	C++14	100 / 100	2191 ms	61784 KiB

chorus

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
 
vector<int> a,b,pre,lx;
int n;
typedef pair<int,int> pii;
bool check(pii a,pii b,pii c){
    return (b.sc-a.sc)*(b.fs-c.fs)>(c.sc-b.sc)*(a.fs-b.fs);
}
bool check2(pii a,pii b,int c){
    return a.fs*c+a.sc>b.fs*c+b.sc;
}
pii get(int p){
    vector<pii> dp(n+1,{1e18,1e18});
    //dp[i] = min(dp[j]+pre[i]+(cost)-b[j+1]*i);
    // -2 1 3 4 5 8 11 
    // -1 2 6 7 9 10 12
    // 6 -> 1 = dp[1]+pre_a[6]+(6-1+6-3+6-4+6-5)-6*6 = 2+5 = 7+dp[1]
    // 4 -> 1: because 5 < 6, so the cost is 0
    // when 1 is available, lx[1] = 4 and update with 4*6-pre[4];
    // s dec, qu inc;
    //
    dp[0]={0,0};
    deque<pii> li;
    deque<int> dz;
    int f=1;
    for(int i=1;i<=n;i++){
        while(f<i && lx[f]<i){
            pii ad(-2*b[f]+2*lx[f]+1,2*(dp[f-1].fs+(i-1)*b[f]-pre[i-1])-lx[f]*lx[f]-lx[f]);
            while(li.size()>=2 && check(li[li.size()-2],li.back(),ad)){
                li.pop_back();
                dz.pop_back();
            }
            li.push_back(ad);
            dz.push_back(f-1);
            f++;
        }
        while(li.size()>=2 && check2(li[0],li[1],i)){
            li.pop_front();
            dz.pop_front();
        }
        if(li.size()){
            dp[i].fs=(li[0].fs*i+li[0].sc+2*pre[i]+2*p-i*i)/2;
            dp[i].sc=dp[dz[0]].sc+1;
        }
        else{
            dp[i]={p,1};
        }
        dp[i]=min(dp[i],pii(dp[f-1].fs+p,dp[f-1].sc+1));
    }   
    return dp[n];
}
signed main(){
    AquA;
    int k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans=0,cnt=0,cs=0,tmp=0;
    a.push_back(-2);
    b.push_back(-1);
    for(int i=0;i<2*n;i++){
        if(s[i]=='A'){
            cnt++;
            a.push_back(cs);
            ans+=i-cs;
            cs++;
            if(tmp>0){
                tmp--;
                b.push_back(cs);
                cnt--;
                cs++;
            }
        }
        else{
            if(cnt==0){
                tmp++;
            }
            else{
                cnt--;
                b.push_back(cs);
                cs++;
            }
        }
    }
    pre=a;
    lx.resize(n+2);
    a.push_back(998244353);
    b.push_back(998244354);
    for(int i=1;i<=n;i++){
        lx[i]=lx[i-1];
        while(lx[i]+1<a.size() && a[lx[i]+1]<=b[i]){
            lx[i]++;
        }
    }
    for(int i=2;i<=n;i++){
        pre[i]+=pre[i-1];
    }
    int l=0,r=1e18;
    while(r>l){
        int m=(l+r)/2;
        auto u=get(m);
        if(u.sc<=k){
            r=m;
        }
        else{
            l=m+1;
        }
    }
    auto z=get(l);
    cout << ans+(z.fs-k*l) << "\n";
    return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:98:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         while(lx[i]+1<a.size() && a[lx[i]+1]<=b[i]){

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