Submission #935158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
935158	2024-02-28T18:07:27 Z	kim	Chorus (JOI23_chorus)	C++17	40 / 100	7000 ms	12892 KB

chorus

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second

const ll inf=1e18;

int a[1000005],b[1000005],pos[1000005],pos2[1000005];
ll dp[2][1000005],qs[1000005];

ll f(int L,int R){
    int x=pos2[L];
    if(x>R) return 0;
    return qs[R]-qs[x-1]-L*(R-x+1);
}

void play2(int n,bool z){
    for(int i=1;i<=n;++i){
        dp[z][i]=inf;
        for(int j=0;j<i;++j){
            if(pos2[j]>i){
                dp[z][i]=min(dp[z][i],dp[!z][j]);
                break;
            }
            dp[z][i]=min(dp[z][i],dp[!z][j]+qs[i]-qs[pos2[j+1]-1]-1LL*(j+1)*(i-pos2[j+1]+1));
        }
    }
}

void play(int l,int r,int optl,int optr,int z){
    if(l>r) return;
    int mid=l+r>>1;
    pair<ll,int> best(inf,0);
    for(int i=optl;i<=min(mid,optr);++i){
        best=min(best,{dp[!z][i-1]+f(i,mid),i});
    }
    dp[z][mid]=best.f;
    play(l,mid-1,optl,best.s,z);
    play(mid+1,r,best.s,optr,z);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int n,K; cin>>n>>K;
    string s; cin>>s;
    for(int i=0,ia=0,ib=0;i<s.length();++i){
        if(s[i]=='A') a[++ia]=i;
        else b[++ib]=i;
    }
    for(int i=1,j=1;i<=n;++i){
        while(j<=n&&b[j]<a[i]) ++j;
        pos[i]=j;
        qs[i]=qs[i-1]+j;
    }
    for(int i=1,j=1;i<=n;++i){
        while(j<=n&&pos[j]<=i) ++j;
        j=max(i,j);
        pos2[i]=j;
    }
    for(int i=1;i<=n;++i) dp[1][i]=qs[i]-i;
    for(int k=2;k<=K;++k){
        // play(1,n,1,n,k&1);
        play2(n,k&1);
    }
    cout<<dp[K&1][n]<<endl;

    return 0;
}

Compilation message

chorus.cpp: In function 'void play(int, int, int, int, int)':
chorus.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid=l+r>>1;
      |             ~^~
chorus.cpp: In function 'int main()':
chorus.cpp:49:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0,ia=0,ib=0;i<s.length();++i){
      |                           ~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12788 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	1 ms	10584 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	10588 KB	Output is correct
10	Correct	2 ms	12636 KB	Output is correct
11	Correct	2 ms	12636 KB	Output is correct
12	Correct	2 ms	12636 KB	Output is correct
13	Correct	2 ms	12632 KB	Output is correct
14	Correct	2 ms	12636 KB	Output is correct
15	Correct	2 ms	12632 KB	Output is correct
16	Correct	2 ms	12892 KB	Output is correct

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12788 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	1 ms	10584 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	10588 KB	Output is correct
10	Correct	2 ms	12636 KB	Output is correct
11	Correct	2 ms	12636 KB	Output is correct
12	Correct	2 ms	12636 KB	Output is correct
13	Correct	2 ms	12632 KB	Output is correct
14	Correct	2 ms	12636 KB	Output is correct
15	Correct	2 ms	12632 KB	Output is correct
16	Correct	2 ms	12892 KB	Output is correct
17	Correct	3 ms	12636 KB	Output is correct
18	Correct	23 ms	12636 KB	Output is correct
19	Correct	56 ms	12636 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	12756 KB	Output is correct
22	Correct	106 ms	12752 KB	Output is correct
23	Correct	106 ms	12748 KB	Output is correct
24	Correct	4 ms	12632 KB	Output is correct
25	Correct	106 ms	12748 KB	Output is correct
26	Correct	89 ms	12748 KB	Output is correct
27	Correct	36 ms	12632 KB	Output is correct
28	Correct	43 ms	12632 KB	Output is correct

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12788 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	1 ms	10584 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	10588 KB	Output is correct
10	Correct	2 ms	12636 KB	Output is correct
11	Correct	2 ms	12636 KB	Output is correct
12	Correct	2 ms	12636 KB	Output is correct
13	Correct	2 ms	12632 KB	Output is correct
14	Correct	2 ms	12636 KB	Output is correct
15	Correct	2 ms	12632 KB	Output is correct
16	Correct	2 ms	12892 KB	Output is correct
17	Correct	3 ms	12636 KB	Output is correct
18	Correct	23 ms	12636 KB	Output is correct
19	Correct	56 ms	12636 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	12756 KB	Output is correct
22	Correct	106 ms	12752 KB	Output is correct
23	Correct	106 ms	12748 KB	Output is correct
24	Correct	4 ms	12632 KB	Output is correct
25	Correct	106 ms	12748 KB	Output is correct
26	Correct	89 ms	12748 KB	Output is correct
27	Correct	36 ms	12632 KB	Output is correct
28	Correct	43 ms	12632 KB	Output is correct
29	Execution timed out	7087 ms	12632 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12788 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	1 ms	10584 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	10588 KB	Output is correct
10	Correct	2 ms	12636 KB	Output is correct
11	Correct	2 ms	12636 KB	Output is correct
12	Correct	2 ms	12636 KB	Output is correct
13	Correct	2 ms	12632 KB	Output is correct
14	Correct	2 ms	12636 KB	Output is correct
15	Correct	2 ms	12632 KB	Output is correct
16	Correct	2 ms	12892 KB	Output is correct
17	Correct	3 ms	12636 KB	Output is correct
18	Correct	23 ms	12636 KB	Output is correct
19	Correct	56 ms	12636 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	12756 KB	Output is correct
22	Correct	106 ms	12752 KB	Output is correct
23	Correct	106 ms	12748 KB	Output is correct
24	Correct	4 ms	12632 KB	Output is correct
25	Correct	106 ms	12748 KB	Output is correct
26	Correct	89 ms	12748 KB	Output is correct
27	Correct	36 ms	12632 KB	Output is correct
28	Correct	43 ms	12632 KB	Output is correct
29	Execution timed out	7087 ms	12632 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12788 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	1 ms	10584 KB	Output is correct
6	Correct	2 ms	12636 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	10588 KB	Output is correct
10	Correct	2 ms	12636 KB	Output is correct
11	Correct	2 ms	12636 KB	Output is correct
12	Correct	2 ms	12636 KB	Output is correct
13	Correct	2 ms	12632 KB	Output is correct
14	Correct	2 ms	12636 KB	Output is correct
15	Correct	2 ms	12632 KB	Output is correct
16	Correct	2 ms	12892 KB	Output is correct
17	Correct	3 ms	12636 KB	Output is correct
18	Correct	23 ms	12636 KB	Output is correct
19	Correct	56 ms	12636 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	12756 KB	Output is correct
22	Correct	106 ms	12752 KB	Output is correct
23	Correct	106 ms	12748 KB	Output is correct
24	Correct	4 ms	12632 KB	Output is correct
25	Correct	106 ms	12748 KB	Output is correct
26	Correct	89 ms	12748 KB	Output is correct
27	Correct	36 ms	12632 KB	Output is correct
28	Correct	43 ms	12632 KB	Output is correct
29	Execution timed out	7087 ms	12632 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Submission #935158

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0