Submission #915890

#	Time	Username	Problem	Language	Result	Execution time	Memory
915890		efedmrlr	Chorus (JOI23_chorus)	C++17	61 / 100	2592 ms	1884 KiB

chorus

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 5e3+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q,K;

vector<int> a(1), b(1);
vector<int> acnt(2*N, 0);
lli ans = 0;
vector<int> dp, dpn;
vector<int> xs(N, 0);
vector<int> sum(N, 0);
struct SegT {
    vector<int> data;
    int sz;
    SegT() {}

    void build(int tl, int tr, int v, vector<int> &vec) {
        if(tl == tr) {
            data[v] = vec[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(tl, tm, v<<1, vec);
        build(tm + 1, tr, v<<1^1, vec);
        data[v] = min(data[v<<1], data[v<<1^1]);
    }
    void reset(int s) {
        sz = s;
        data.assign(4*sz + 5, INF);
    }
    int query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v];
        }
        if(tl > r || tr < l) {
            return INF;
        }
        int tm = (tl + tr) >> 1;
        return min(query(tl, tm, v<<1, l, r), query(tm + 1, tr, v<<1^1, l, r));
    }
    int query(int l, int r) {
        if(l > r) return INF;
        return query(1, sz, 1, l, r);
    }
};

string s;

struct Line {
    int a, b;
    Line(int ax, int bx) : a(ax), b(bx) {}
    Line() : a(0), b(0) {}
    long double intersect(Line &oth) {
        return (long double)(b - oth.b) / (oth.a - a);
    }
    int eval(int x) {
        return a*x + b;
    }
};

struct CHT {
    deque<Line> cht;
    CHT() {}
    void reset() {
        cht.clear();
    }
    void update(Line nw) {
        while(cht.size() > 1 && cht.front().intersect(cht[1]) > cht.front().intersect(nw)) {
            cht.pop_front();
        }
        cht.push_front(nw);
    }
    int query(int x) {
        while(cht.size() > 1 && cht.back().intersect(cht[cht.size() - 2]) < (long double)x) {
            cht.pop_back();
        }
        return cht.back().eval(x);
    }

    
};
SegT st;
CHT cht;
inline void solve() {
    cin>>n>>K;
    cin>>s;
    
    for(int i = 0; i<2*n; i++) {
        acnt[i + 1] = acnt[i] + (s[i] == 'A');
        if(s[i] == 'A') {
            a.pb(i + 1);
        }
        else {
            b.pb(i + 1);
        }
    }
    
    for(int i = 1; i<=n; i++) {
        if(a[i] < b[i]) continue;
        int tmp = acnt[a[i]] - acnt[b[i]];
        ans += tmp;
    }
    s.clear(); s.pb('0');
    int cnt = 0;
    for(int i = 1; i<=n; i++) {
        while(cnt < acnt[max(a[i], b[i])]) {
            s.pb('A');
            cnt++;
        }
        s.pb('B');
    }
    a.clear(); b.clear(); a.pb(0); b.pb(0);
    // cout<<s<<"\n";
    // cout<<ans<<"\n";
    for(int i = 1; i<=2*n; i++) {
        acnt[i] = acnt[i - 1] + (s[i] == 'A');
        if(s[i] == 'A') {
            a.pb(i);
        }
        else {
            b.pb(i);
        }
    }
    // for(int i = 1; i<=n; i++) {
    //     cout<<a[i]<<" "<<b[i]<<"\n";
    // }
    for(int i = 1; i<=n; i++) {
        int itr = (int)(upper_bound(all(b), a[i]) - b.begin());
        xs[i] = itr;
    }
    for(int i = 1; i<=n; i++) {
        sum[i] = sum[i - 1] + acnt[b[i]];
    }
    dp.assign(n + 1, INF);
    dpn.assign(n + 1, INF);
    dp[0] = 0;
    st.reset(n);
    for(int k = 1; k<=K; k++) {
        st.build(1, n, 1, dp);
        cht.reset();
        int itr = 1;
        for(int i = 1; i<=n; i++) {
            dpn[i] = INF;
            int x = xs[i];
            
            dpn[i] = min(dpn[i] , st.query(x, i - 1));
            while(itr <= xs[i]) {
                cht.update(Line(-itr, sum[itr - 1] + dp[itr - 1]));
                itr++;
            }
            if(cht.cht.size()) {
                dpn[i] = min(dpn[i], x * acnt[a[i]] - sum[x - 1] + cht.query(acnt[a[i]]));
            }
            // cout<<"k:"<<k<<" "<<i<<" res: "<<dpn[i]<<"\n";
        }
        swap(dp, dpn);
        dp[0] = INF;
    }
    cout<<dp[n] + ans<<"\n";
}
 
signed main() {

    //fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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