oj.uz

Submission #825425

# Submission time Handle Problem Language Result Execution time Memory
825425 2023-08-14T20:01:08 Z grogu Chorus (JOI23_chorus) C++14
16 / 100
 22 ms 47328 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int64_t
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;


#define maxn 1000005
ll n,k;
ll a[2*maxn];
ll c[maxn];
ll ps[maxn];
ll sz = 0;
ll dp[maxn];
struct line{
    ll n,k,cnti;
    line(){n = llinf;k = 0;cnti = 0;}
    line(ll n_,ll k_,ll cnti_){n = n_,k = k_,cnti = cnti_;}
    ll operator()(ll x){
        return k*x+n;
    }
};
line t[2*maxn];
ll ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    t[v] = line();
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,line f){
    line g = t[v];
    if(tl==tr){
        if(f(tl)<g(tl)) t[v] = f;
        return;
    }
    ll mid = (tl+tr)/2;
    if(f(tl)>g(tl)) swap(f,g);
    if(f(mid)<=g(mid)){t[v] = f;upd(rs[v],mid+1,tr,g);}
    else{t[v] = g;upd(ls[v],tl,mid,f);}
}
line mini(line f,line g,ll i){
    if(f(i)<g(i)) return f;
    return g;
}
line get(ll v,ll tl,ll tr,ll i){
    if(tl==tr) return t[v];
    ll mid = (tl+tr)/2;
    if(i<=mid) return mini(get(ls[v],tl,mid,i),t[v],i);
    return mini(get(rs[v],mid+1,tr,i),t[v],i);
}
ll cnt[maxn];
ll check(ll x){
    multiset<pll> s;
    init(root,1,n);
    ll e = 1;
    s.insert({0,0});
    dp[0] = 0;
    cnt[0] = 0;
    for(ll i = 1;i<=n;i++){
        while(e<=i&&c[e]<=i){
            s.erase(s.find({dp[e-1],cnt[e-1]}));
            line f(ps[e-1]+dp[e-1],-e,cnt[e-1]);
            upd(root,1,n,f);
            e++;
        }
        dp[i] = llinf; cnt[i] = 0;
        if(si(s)){
            dp[i] = (*s.begin()).fi + x;
            cnt[i] = (*s.begin()).sc + 1;
        }
        line f = get(root,1,n,i);
        if(f(i) - ps[e-1] + e*i + x < dp[i]){
            dp[i] = f(i) - ps[e-1] + e*i + x;
            cnt[i] = f.cnti+1;
        }
        s.insert({dp[i],cnt[i]});
    }
    return cnt[n];
}
ll bs(){
    ll l = 0,r = llinf/100,mid,rez = 0;
    while(l<=r){
        mid = (l+r)/2;
        ll e = check(mid);
        if(e<=k){
            r = mid-1;
            rez = mid;
        }else{
            l = mid+1;
        }
    }
    check(rez);
    return dp[n]-k*rez;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> k;
    string s; cin >> s;
    for(ll i = 1;i<=2*n;i++){
        if(s[i-1]=='A') a[i] = 1;
    }
    ll b = 0;
    for(ll i = 2*n;i>=1;i--){
        if(a[i]==1){
            c[++sz] = b;
        }else b++;
    }
    for(ll i = 1;i<=n;i++) ps[i] = ps[i-1] + c[i];
    //for(ll i = 0;i<=n;i++) ceri(dp[i],0,k);
    cout<<bs()<<endl;
	return (0-0);
}
/**
5 2
AABABABBAB

10 9
BBBBBBBBBBAAAAAAAAAA



**/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 21 ms 47304 KB Output is correct
4 Correct 21 ms 47220 KB Output is correct
5 Correct 19 ms 47224 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47308 KB Output is correct
9 Correct 20 ms 47220 KB Output is correct
10 Correct 21 ms 47316 KB Output is correct
11 Correct 20 ms 47260 KB Output is correct
12 Correct 20 ms 47244 KB Output is correct
13 Correct 21 ms 47200 KB Output is correct
14 Correct 22 ms 47316 KB Output is correct
15 Correct 20 ms 47248 KB Output is correct
16 Correct 20 ms 47328 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 21 ms 47304 KB Output is correct
4 Correct 21 ms 47220 KB Output is correct
5 Correct 19 ms 47224 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47308 KB Output is correct
9 Correct 20 ms 47220 KB Output is correct
10 Correct 21 ms 47316 KB Output is correct
11 Correct 20 ms 47260 KB Output is correct
12 Correct 20 ms 47244 KB Output is correct
13 Correct 21 ms 47200 KB Output is correct
14 Correct 22 ms 47316 KB Output is correct
15 Correct 20 ms 47248 KB Output is correct
16 Correct 20 ms 47328 KB Output is correct
17 Incorrect 21 ms 47248 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 21 ms 47304 KB Output is correct
4 Correct 21 ms 47220 KB Output is correct
5 Correct 19 ms 47224 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47308 KB Output is correct
9 Correct 20 ms 47220 KB Output is correct
10 Correct 21 ms 47316 KB Output is correct
11 Correct 20 ms 47260 KB Output is correct
12 Correct 20 ms 47244 KB Output is correct
13 Correct 21 ms 47200 KB Output is correct
14 Correct 22 ms 47316 KB Output is correct
15 Correct 20 ms 47248 KB Output is correct
16 Correct 20 ms 47328 KB Output is correct
17 Incorrect 21 ms 47248 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 21 ms 47304 KB Output is correct
4 Correct 21 ms 47220 KB Output is correct
5 Correct 19 ms 47224 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47308 KB Output is correct
9 Correct 20 ms 47220 KB Output is correct
10 Correct 21 ms 47316 KB Output is correct
11 Correct 20 ms 47260 KB Output is correct
12 Correct 20 ms 47244 KB Output is correct
13 Correct 21 ms 47200 KB Output is correct
14 Correct 22 ms 47316 KB Output is correct
15 Correct 20 ms 47248 KB Output is correct
16 Correct 20 ms 47328 KB Output is correct
17 Incorrect 21 ms 47248 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47316 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 21 ms 47304 KB Output is correct
4 Correct 21 ms 47220 KB Output is correct
5 Correct 19 ms 47224 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 20 ms 47276 KB Output is correct
8 Correct 20 ms 47308 KB Output is correct
9 Correct 20 ms 47220 KB Output is correct
10 Correct 21 ms 47316 KB Output is correct
11 Correct 20 ms 47260 KB Output is correct
12 Correct 20 ms 47244 KB Output is correct
13 Correct 21 ms 47200 KB Output is correct
14 Correct 22 ms 47316 KB Output is correct
15 Correct 20 ms 47248 KB Output is correct
16 Correct 20 ms 47328 KB Output is correct
17 Incorrect 21 ms 47248 KB Output isn't correct
18 Halted 0 ms 0 KB -