oj.uz

Submission #925111

# Submission time Handle Problem Language Result Execution time Memory
925111 2024-02-10T19:08:58 Z ttamx Chorus (JOI23_chorus) C++14
0 / 100
 1 ms 4680 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;

const int N=1e6+5;

ll n,k;
string s;
ll a[N],b[N];
ll qs[N];
pl dp[N];

struct CHT{
    struct Line{
        ll m,c,cnt;
        Line(ll m,ll c,ll cnt):m(m),c(c),cnt(cnt){}
        ll get(ll x){
            return m*x+c;
        }
    };
    deque<Line> dq;
    bool bad(Line l1,Line l2,Line l3){
        return (l2.c-l1.c)*(l3.m-l1.m)<(l3.c-l1.c)*(l2.m-l1.m);
    }
    void clear(){
        dq.clear();
    }
    void insert(ll m,ll c,int cnt){
        Line l(m,c,cnt);
        while(dq.size()>1&&bad(dq.end()[-2],dq.back(),l))dq.pop_back();
        dq.emplace_back(l);
    }
    pl query(ll x){
        while(dq.size()>1&&dq[0].get(x)>dq[1].get(x))dq.pop_front();
        return pl(dq[0].get(x),dq[0].cnt);
    }
}cht;

pl solve(ll lambda){
    cht.clear();
    cht.insert(0,0,0);
    deque<int> dq;
    for(int i=1;i<=n;i++){
        while(!dq.empty()&&b[dq.front()]<i){
            int j=dq.front();
            dq.pop_front();
            cht.insert(-j,dp[j].first-qs[b[j]]+j*b[j],dp[j].second);
        }
        dp[i]=cht.query(i);
        dp[i].first+=qs[i];
        if(!dq.empty())dp[i]=min(dp[i],dp[dq.front()]);
        dp[i].first+=lambda;
        dp[i].second++;
        dq.emplace_back(i);
    }
    return dp[n];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> s;
    for(int i=0,ia=0,ib=0;i<2*n;i++){
        if(s[i]=='A'){
            a[++ia]=ib;
        }else{
            ib++;
        }
    }
    for(int i=1,p=1;i<=n;i++){
        while(p<=n&&a[p]<i)p++;
        b[i]=max(i,p-1);
    }
    for(int i=1;i<=n;i++)qs[i]=qs[i-1]+a[i];
    ll l=0,r=n*n;
    while(l<r){
        ll m=(l+r+1)/2;
        if(solve(m).second>=k)l=m;
        else r=m-1;
    }
    cout << solve(l).first-k*l;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4680 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4680 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4680 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4680 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4680 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -