oj.uz

답안 #925103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925103 2024-02-10T18:54:23 Z ttamx Chorus (JOI23_chorus) C++14
0 / 100
 1 ms 4444 KB 
#include<bits/stdc++.h>

using namespace std;

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

const int N=1e6+5;

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

struct Line{
    ll m,c,cnt;
    Line(ll _m,ll _c,ll _cnt):m(_m),c(_c),cnt(_cnt){}
    ll eval(ll x){
        return m*x+c;
    }
};

struct CHT{
    deque<Line> hull;
    bool bad(Line x,Line y,Line z){
        return (x.c-y.c)*(z.m-x.m)>(x.c-z.c)*(y.m-x.m);
    }
    void insert(ll m,ll c,ll cnt){
        Line v(m,c,cnt);
        while(hull.size()>1&&bad(hull.end()[-2],hull.back(),v))hull.pop_back();
        hull.emplace_back(v);
    }
    pl query(ll x){
        while(hull.size()>1&&hull[0].eval(x)>hull[1].eval(x))hull.pop_front();
        return pl(hull[0].eval(x),hull[0].cnt);
    }
};

pl solve(ll lambda){
    CHT cht;
    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]]+1LL*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++;
            b[ib]=max(ib,ia);
        }
    }
    for(int i=1;i<=n;i++)qs[i]=qs[i-1]+a[i];
    ll l=0,r=1LL*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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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 -