Submission #891958

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891958	2023-12-24T13:57:00 Z	alexander707070	Chorus (JOI23_chorus)	C++14	40 / 100	25 ms	103372 KB

chorus

#include<bits/stdc++.h>
#define MAXN 5007
using namespace std;

const long long inf=1e15;

int n,k;
long long ans;
char s[MAXN];

long long dp[MAXN][MAXN];
int opt[MAXN][MAXN],pref[MAXN];
long long sum[MAXN][MAXN],sum2[MAXN][MAXN];

long long cost(int l,int r){
    if((r-l+1)%2!=0)return inf;

    return (sum[(r-l+1)/2][(l+r)/2] - sum[0][(l+r)/2-(r-l+1)/2] + sum2[(r-l+1)/2-1][(l+r)/2+1])/2;    
}

void solve(int l,int r,int optl,int optr,int k){
    if(l>r)return;

    int mid=((l+r)/2)*2;

    dp[mid][k]=inf;
    opt[mid][k]=optr;

    for(int i=min(mid,optr);i>=optl;i--){
        if(dp[i-1][k-1]+cost(i,mid)<dp[mid][k]){
            dp[mid][k]=dp[i-1][k-1]+cost(i,mid);
            opt[mid][k]=i;
        }
    }

    solve(l,mid/2-1,optl,opt[mid][k],k);
    solve(mid/2+1,r,opt[mid][k],optr,k);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k; 
    n*=2;
    cin>>(s+1);

    for(int i=1;i<=n;i++){
        if(s[i]=='A')pref[i]++;
        else pref[i]--;
        pref[i]+=pref[i-1];
    }

    for(int i=0;i<=n/2;i++){
        for(int f=1;f<=n;f++){
            sum[i][f]=max(i-pref[f],0);
            if(i>0)sum[i][f]+=sum[i-1][f-1];

            sum2[i][f]=max(i-pref[f],0);
            if(i>0)sum2[i][f]+=sum2[i-1][f+1];
        }
    }

    for(int i=1;i<=n;i++){
        dp[i][0]=inf;
    }

    ans=inf;
    for(int i=1;i<=k;i++){
        solve(1,n/2,1,n,i);
        ans=min(ans,dp[n][i]);
    }

    cout<<ans<<"\n";

    return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6488 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6488 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	5 ms	37468 KB	Output is correct
18	Correct	16 ms	103260 KB	Output is correct
19	Correct	19 ms	103256 KB	Output is correct
20	Correct	11 ms	103256 KB	Output is correct
21	Correct	13 ms	103220 KB	Output is correct
22	Correct	25 ms	103372 KB	Output is correct
23	Correct	24 ms	103256 KB	Output is correct
24	Correct	11 ms	103260 KB	Output is correct
25	Correct	25 ms	103260 KB	Output is correct
26	Correct	23 ms	103260 KB	Output is correct
27	Correct	16 ms	103300 KB	Output is correct
28	Correct	17 ms	103260 KB	Output is correct

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6488 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6488 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	5 ms	37468 KB	Output is correct
18	Correct	16 ms	103260 KB	Output is correct
19	Correct	19 ms	103256 KB	Output is correct
20	Correct	11 ms	103256 KB	Output is correct
21	Correct	13 ms	103220 KB	Output is correct
22	Correct	25 ms	103372 KB	Output is correct
23	Correct	24 ms	103256 KB	Output is correct
24	Correct	11 ms	103260 KB	Output is correct
25	Correct	25 ms	103260 KB	Output is correct
26	Correct	23 ms	103260 KB	Output is correct
27	Correct	16 ms	103300 KB	Output is correct
28	Correct	17 ms	103260 KB	Output is correct
29	Runtime error	15 ms	348 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6488 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6488 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	5 ms	37468 KB	Output is correct
18	Correct	16 ms	103260 KB	Output is correct
19	Correct	19 ms	103256 KB	Output is correct
20	Correct	11 ms	103256 KB	Output is correct
21	Correct	13 ms	103220 KB	Output is correct
22	Correct	25 ms	103372 KB	Output is correct
23	Correct	24 ms	103256 KB	Output is correct
24	Correct	11 ms	103260 KB	Output is correct
25	Correct	25 ms	103260 KB	Output is correct
26	Correct	23 ms	103260 KB	Output is correct
27	Correct	16 ms	103300 KB	Output is correct
28	Correct	17 ms	103260 KB	Output is correct
29	Runtime error	15 ms	348 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	6492 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	6488 KB	Output is correct
10	Correct	1 ms	6492 KB	Output is correct
11	Correct	1 ms	6492 KB	Output is correct
12	Correct	1 ms	6492 KB	Output is correct
13	Correct	1 ms	6492 KB	Output is correct
14	Correct	1 ms	6488 KB	Output is correct
15	Correct	1 ms	6492 KB	Output is correct
16	Correct	1 ms	6492 KB	Output is correct
17	Correct	5 ms	37468 KB	Output is correct
18	Correct	16 ms	103260 KB	Output is correct
19	Correct	19 ms	103256 KB	Output is correct
20	Correct	11 ms	103256 KB	Output is correct
21	Correct	13 ms	103220 KB	Output is correct
22	Correct	25 ms	103372 KB	Output is correct
23	Correct	24 ms	103256 KB	Output is correct
24	Correct	11 ms	103260 KB	Output is correct
25	Correct	25 ms	103260 KB	Output is correct
26	Correct	23 ms	103260 KB	Output is correct
27	Correct	16 ms	103300 KB	Output is correct
28	Correct	17 ms	103260 KB	Output is correct
29	Runtime error	15 ms	348 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Submission #891958

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