Submission #1083230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083230		kes0716	Chorus (JOI23_chorus)	C++17	0 / 100	10 ms	14988 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
char s[2000009];
typedef long long ll;
const ll INF = (ll)3e18;
ll a[1000009], psum[1000009], dp[1000009];
int cnt[1000009];
int tree[1<<21]; //(i, j) -> dp[i][j] + cost(j, *)
ll cost(int k, int j){
    int idx = lower_bound(a+k, a+j, k-1) - a;
    return psum[j-1] - psum[idx-1] - (ll)(k-1) * (j-idx);
}
pair<ll, int> evaluate(int idx, int x){
    if(idx == -1)
        return make_pair(INF, 0);
    return make_pair(dp[idx] + 2*cost(idx, x), cnt[idx] + 1);
}
void update(int v, int l, int r, int idx){
    int mid = (l+r)/2;
    if(evaluate(tree[v], mid) > evaluate(idx, mid))
        swap(idx, tree[v]);
    if(evaluate(idx, l).first < evaluate(tree[v], l).first)
        update(2*v, l, mid, idx);
    else if(evaluate(idx, r).first < evaluate(tree[v], r).first)
        update(2*v+1, mid+1, r, idx);
}
pair<ll, int> query(int v, int l, int r, int x){
    pair<ll, int> ans = evaluate(tree[v], x);
    int mid = (l+r)/2;
    if(l==r)
        return ans;
    if(x <= mid)
        ans = min(ans, query(2*v, l, mid, x));
    if(x > mid)
        ans = min(ans, query(2*v+1, mid+1, r, x));
    return ans;
}
int main(){
    int n, k, i, j, j2, cur = 0, cnt2 = 0;
    scanf("%d %d", &n, &k);
    scanf(" %s", s);
    for(i=0; i<2*n; i++){
        if(s[i] == 'A'){
            a[++cnt2] = cur;
        }
        else
            cur++;
    }
    for(i=1; i<=n; i++)
        psum[i] = psum[i-1] + a[i];
    ll lo = 0, hi = (ll)1e12, lambda;
    while(1){
        memset(tree, -1, sizeof(tree));
        lambda = (lo+hi)>>1;
        dp[1] = 0;
        update(1, 1, n+1, 1);
        for(j=2; j<=n+1; j++){
           pair<ll, int> temp = query(1, 1, n+1, j);
           dp[j] = min(INF, 2*lambda+1+temp.first);
           cnt[j]= temp.second;
           //printf("j=%d dp=%lld cnt=%d\n", j, dp[j], cnt[j]);
           update(1, 1, n+1, j);
        }
        if(lo==hi)
            break;
        if(cnt[n+1] > k)
            lo = lambda+1;
        else
            hi = lambda;
    }
    memset(tree, -1, sizeof(tree));
    lambda = lo;
    dp[1] = 0;
    update(1, 1, n+1, 1);
    for(j=2; j<=n+1; j++){
       pair<ll, int> temp = query(1, 1, n+1, j);
       dp[j] = min(INF, 2*lambda+temp.first);
       cnt[j]= temp.second;
       update(1, 1, n+1, j);
    }
	assert((dp[n+1] - cnt[n+1]*(2*lambda)) % 2 == 0);
    printf("%lld\n", (dp[n+1] - cnt[n+1]*(2*lambda))>>1);
    return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:39:21: warning: unused variable 'j2' [-Wunused-variable]
   39 |     int n, k, i, j, j2, cur = 0, cnt2 = 0;
      |                     ^~
chorus.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~

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