Submission #834708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834708	2023-08-22T17:31:57 Z	alvingogo	Chorus (JOI23_chorus)	C++14	40 / 100	6 ms	596 KB

chorus

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
 
vector<int> a,b,pre,lx;
int n;
typedef pair<int,int> pii;
bool check(pii a,pii b,pii c){
    return (b.sc-a.sc)*(b.fs-c.fs)>=(c.sc-b.sc)*(a.fs-b.fs);
}
bool check2(pii a,pii b,int c){
    return a.fs*c+a.sc>=b.fs*c+b.sc;
}
pii get(int p){
    vector<pii> dp(n+1,{1e18,1e18});
    //dp[i] = min(dp[j]+pre[i]+(cost)-b[j+1]*i);
    // -2 1 3 4 5 8 11 
    // -1 2 6 7 9 10 12
    // 6 -> 1 = dp[1]+pre_a[6]+(6-1+6-3+6-4+6-5)-6*6 = 2+5 = 7+dp[1]
    // 4 -> 1: because 5 < 6, so the cost is 0
    // when 1 is available, lx[1] = 4 and update with 4*6-pre[4];
    // s dec, qu inc;
    //
    dp[0]={0,0};
    deque<pii> li;
    deque<int> dz;
    int f=1;
    for(int i=1;i<=n;i++){
        while(f<i && lx[f]<i){
            pii ad(-2*b[f]+2*lx[f]+1,2*(dp[f-1].fs+(i-1)*b[f]-pre[i-1])-lx[f]*lx[f]-lx[f]);
            while(li.size()>=2 && check(li[li.size()-2],li.back(),ad)){
                li.pop_back();
                dz.pop_back();
            }
            li.push_back(ad);
            dz.push_back(f-1);
            f++;
        }
        while(li.size()>=2 && check2(li[0],li[1],i)){
            li.pop_front();
            dz.pop_front();
        }
        if(li.size()){
            dp[i].fs=(li[0].fs*i+li[0].sc+2*pre[i]+2*p-i*i)/2;
            dp[i].sc=dp[dz[0]].sc+1;
        }
        else{
            dp[i]={p,1};
        }
        dp[i]=min(dp[i],pii(dp[f-1].fs+p,dp[f-1].sc+1));
    }   
    return dp[n];
}
signed main(){
    AquA;
    int k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans=0,cnt=0,cs=0,tmp=0;
    a.push_back(-2);
    b.push_back(-1);
    for(int i=0;i<2*n;i++){
        if(s[i]=='A'){
            cnt++;
            a.push_back(cs);
            ans+=i-cs;
            cs++;
            if(tmp>0){
                tmp--;
                b.push_back(cs);
                cnt--;
                cs++;
            }
        }
        else{
            if(cnt==0){
                tmp++;
            }
            else{
                cnt--;
                b.push_back(cs);
                cs++;
            }
        }
    }
    pre=a;
    lx.resize(n+2);
    a.push_back(998244353);
    b.push_back(998244354);
    for(int i=1;i<=n;i++){
        lx[i]=lx[i-1];
        while(lx[i]+1<a.size() && a[lx[i]+1]<=b[i]){
            lx[i]++;
        }
    }
    for(int i=2;i<=n;i++){
        pre[i]+=pre[i-1];
    }
    int l=0,r=1e18;
    while(r>l){
        int m=(l+r)/2;
        auto u=get(m);
        if(u.sc<=k){
            r=m;
        }
        else{
            l=m+1;
        }
    }
    auto z=get(l);
    cout << ans+(z.fs-k*l) << "\n";
    return 0;
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:98:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         while(lx[i]+1<a.size() && a[lx[i]+1]<=b[i]){

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Correct	2 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	360 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Correct	2 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	360 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Incorrect	6 ms	596 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Correct	2 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	360 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Incorrect	6 ms	596 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Correct	2 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	360 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Incorrect	6 ms	596 KB	Output isn't correct
30	Halted	0 ms	0 KB	-