Submission #926967

#	Time	Username	Problem	Language	Result	Execution time	Memory
926967		MtSaka	Chorus (JOI23_chorus)	C++17	100 / 100	2383 ms	118392 KiB

chorus

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll mod1=998244353;
static constexpr ll mod=1000000007;
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
struct CHT{
    private:
    deque<array<ll,3>>dq;
    ll floor_div(ll x,ll y){
        if(x>=0)return x/y;
        return x/y-(x%y?1:0);
    }
    bool need(array<ll,3>l1,array<ll,3>l2,array<ll,3>add){
        return floor_div(l2[1]-l1[1],l1[0]-l2[0])<floor_div(add[1]-l2[1],l2[0]-add[0]);
    }
    public:
    CHT():dq(){}
    void add(ll a,ll b,ll id){
        array<ll,3>l{a,b,id};
        while(dq.size()>=2&&!need(dq[dq.size()-2],dq[dq.size()-1],l)){
            dq.pop_back();
        }
        dq.emplace_back(l);
    }
    pair<ll,ll>get(ll x){
        if(dq.empty())return {inf,0};
        while(dq.size()>=2&&dq[0][0]*x+dq[0][1]>dq[1][0]*x+dq[1][1]){
            dq.pop_front();
        }
        return pair<ll,ll>{dq[0][0]*x+dq[0][1],dq[0][2]};
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k;cin>>n>>k;
    string s;cin>>s;
    vl ida;
    ida.reserve(n);
    rep(i,2*n){
        if(s[i]=='A')ida.eb(i);
    }
    rep(i,n)ida[i]-=i;
    ll id=0;
    vl idx(n+1);
    rep(i,n+1){
        while(id<n&&ida[id]<i)id++;
        idx[i]=id;
    }
    vl suma(n+1);
    rep(i,n)suma[i+1]=suma[i]+ida[i];
    vector<vl>v(n+1);
    rep(i,n+1){
        v[max(i,idx[i])].eb(i);
    }
    set<ll>st;
    vl bef(n+1,-1);
    rep(i,n){
        st.insert(i);
        for(auto j:v[i])st.erase(j);
        if(st.size())bef[i+1]=*st.begin();
    }
    //cerr<<ida.size()<<" "<<idb.size()<<endl;
    auto f=[&](ll lambda)->pair<ll,ll> {
        vector<pair<ll,ll>>dp(n+1,{inf,inf});
        dp[0]={0,0};
        CHT cht;
        rep(i,1,n+1){
            for(auto j:v[i-1]){
                cht.add(-j,j*(i-1)-suma[i-1]+dp[j].first,dp[j].second);
            }
            auto mi=cht.get(i);mi.second++;mi.first+=suma[i]+lambda;
            chmin(dp[i],mi);
            if(bef[i]!=-1)chmin(dp[i],pair<ll,ll>{dp[bef[i]].first+lambda,dp[bef[i]].second+1});
        }
        return dp[n];
    };
    ll l=-1,r=n*(n-1)/2+1;
    while(r-l>1){
        ll mid=(l+r)/2;
        auto tmp=f(mid);
        if(tmp.second>k)l=mid;
        else r=mid;
    }
    //cerr<<l<<" "<<r<<endl;
    auto b=f(r);
    cout<<b.first-k*r<<endl;
}

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