oj.uz

답안 #1007112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007112 2024-06-24T11:57:56 Z snpmrnhlol Chorus (JOI23_chorus) C++17
0 / 100
 1 ms 6492 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 1e18;
char v[N*2];
ll v2[N],v3[N];
ll ps[N + 1];
pair<ll,ll> dp[N + 1];
ll n,k;
ll cnt = 0,cnt2 = 0;
struct line{
    ll k,b;
};
bool check(line a,line b,line c){
    return (a.b - b.b)*(b.k - c.k) <= (b.b - c.b)*(a.k - b.k);
}
struct CHT{
    vector <line> cht;
    ll sz = 0, pt = 0;
    void init(){
        cht.clear();
        sz = 0;
        pt = 0;
    }
    void add(ll k,ll b){
        while(sz >= 2 && check(cht[cnt - 2],cht[cnt - 1],{k,b})){
            cht.pop_back();
            sz--;
        }
        cht.push_back({k,b});
        sz++;
    }
    ll get(ll x){
        pt = min(pt,sz - 1);
        while(pt < sz - 1 && x*(cht[pt].k - cht[pt + 1].k) <= -(cht[pt].b - cht[pt + 1].b)){
            pt++;
        }
        return cht[pt].k*x + cht[pt].b;
    }
};
pair <ll,ll> check(ll x){
    //cout<<"checking:"<<x<<'\n';
    dp[0] = {0,0};
    for(ll i = 1;i <= n;i++){
        dp[i] = {inf,0};
        for(ll j = i - 1;j >= 0;j--){
            if(v2[j] >= i){
                dp[i] = min(dp[i],{dp[j].first + x,dp[j].second + 1});
                //cout<<i<<"->"<<j<<' '<<dp[j].first + x<<' '<<dp[j].second + 1<<'\n';
            }else{
                dp[i] = min(dp[i],{dp[j].first + x + (i - v2[j])*(n - j) - (ps[i] - ps[v2[j]]),dp[j].second + 1});
                //cout<<i<<"->"<<j<<' '<<dp[j].first<<' '<<x<<' '<<(i - v2[j])*(n - j)<<' '<<(ps[i] - ps[v2[j]])<<' '<<dp[j].second + 1<<'\n';
            }
        }
        //cout<<dp[i].first<<' '<<dp[i].second<<' '<<x<<' '<<i<<'\n';
    }
    return dp[n];
    //cout<<'\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(ll i = 0;i < 2*n;i++){
        cin>>v[i];
        if(v[i] == 'B'){
            v2[cnt] = i - cnt;
            cnt++;
        }
        if(v[i] == 'A'){
            v3[cnt2] = i - cnt2;
            cnt2++;
        }
    }
    for(ll i = 1;i <= n;i++){
        ps[i] = ps[i - 1] + (n - v3[i - 1]);
    }
    ll l = 0,r = inf;
    ll ans = 0;
    while(l != r){
        ll mij = (l + r)/2;
        auto x = check(mij);
        if(x.second > k){
            l = mij + 1;
        }else{
            r = mij;
            ans = dp[n].first - dp[n].second*mij;
        }
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -