QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #179458 | #6338. Chorus | maoyiting | 61 | 366ms | 3940kb | C++14 | 632b | 2023-09-14 21:28:33 | 2023-09-14 21:28:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,k,t,c[N],g[N],ans;
long long f[N];
char s[N<<1];
bool ok(int v){
fill(f+1,f+1+n,1e18);
for(int i=1;i<=n;i++){
int sum=0;
for(int j=i;j<=n;j++){
sum+=max(0,c[j]-(i-1));
if(f[i-1]+sum+v<f[j]) f[j]=f[i-1]+sum+v,g[j]=g[i-1]+1;
}
}
if(g[n]<=k) ans=f[n]-1ll*v*k;
return g[n]<=k;
}
signed main(){
scanf("%d%d%s",&n,&k,s+1);
for(int i=1,b=0;i<=2*n;i++){
if(s[i]=='A') c[++t]=b;
else b++;
}
int l=0,r=1e9;
while(l<=r){
int mid=(l+r)/2;
if(ok(mid)) r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 16
Accepted
Test #1:
score: 16
Accepted
time: 1ms
memory: 3632kb
input:
1 1 BA
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
7 5 ABBAAABBABABBA
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10 3 BABBABAABAABBABBBAAA
output:
26
result:
ok 1 number(s): "26"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
10 2 AAABBABABBAAABBBAABB
output:
11
result:
ok 1 number(s): "11"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
10 1 BBBBBBBBBBAAAAAAAAAA
output:
100
result:
ok 1 number(s): "100"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
10 2 BBBBBBBBBBAAAAAAAAAA
output:
75
result:
ok 1 number(s): "75"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
10 9 BBBBBBBBBBAAAAAAAAAA
output:
56
result:
ok 1 number(s): "56"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10 10 BBBBBBBBBBAAAAAAAAAA
output:
55
result:
ok 1 number(s): "55"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
10 10 ABABABABABABABABABAB
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
10 2 ABAAABABABBBABABABAB
output:
14
result:
ok 1 number(s): "14"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 4 ABAABBAAABBBAAABBBAB
output:
2
result:
ok 1 number(s): "2"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10 4 ABAAABBBAAABBBAABBAB
output:
2
result:
ok 1 number(s): "2"
Subtask #2:
score: 24
Accepted
Dependency #1:
100%
Accepted
Test #13:
score: 24
Accepted
time: 1ms
memory: 3636kb
input:
179 54 AAABABABABBAAABBABBABBABBBAAABAAAAABBBABAAAAABABBBAABBBABABBAABABAABABBBBABAABAABABABBBABBAABABBAABBAABABBAAABAAAAAAAABBAAAAABAAABBBBBBBABBAABBBABABAABBAABBABABABBABAAABABAAABABABBAABABAAABBABABABABABBAAABABBBBBBBAABBBAABABBBBABAABBAAAABAABBABABAABAAABABAAAABBBAABAAABBABABBBABAAABAABBBABBBBBA...
output:
41
result:
ok 1 number(s): "41"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
500 93 ABABAABBBBABAABAABAAAAABABBBBBABABBABAAAABAABBBBABAABBBAAABBABABAAAABAABBABAAABBAAABBBABBAAAAAABABABBBABABBBAABAAABAABABAAABAAABBAAABABBBAABBABBBABBBAABAAAABBBAABBBABAAAAAABABABBBABAAAABBBBBAABBBABAAABAABBBABABAABABBBBABBABBBBBBBABAAAABAABAABBABBBAABBBAAAAAAABBAABAAABBBABBBAAABABBBBAABBBABABB...
output:
235
result:
ok 1 number(s): "235"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
500 273 AAABBABAABAAABABAABBBABAAAABBAAABBABAAABBABABAAAABBBAAABBBAABAABAABBABABABABBAAABBBBBBBAABABBAABABBBAABBBBAAABAAAABABBABBBBBAABAABABAAAABBABABABAAAABBBAAAAABABBAABABABAAABBABAAAABABBBAAABABAABBAABBBAABAABBBAABABBBBABAAABAABBBBABBABAAABABBAABABBABBBBBBBABAABAAAABABABAAABABABABAABBAABBBABBBAAB...
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 4ms
memory: 3688kb
input:
500 1 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
250000
result:
ok 1 number(s): "250000"
Test #17:
score: 0
Accepted
time: 4ms
memory: 3636kb
input:
500 2 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
187500
result:
ok 1 number(s): "187500"
Test #18:
score: 0
Accepted
time: 4ms
memory: 3732kb
input:
500 499 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
125251
result:
ok 1 number(s): "125251"
Test #19:
score: 0
Accepted
time: 4ms
memory: 3640kb
input:
500 500 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
125250
result:
ok 1 number(s): "125250"
Test #20:
score: 0
Accepted
time: 4ms
memory: 3820kb
input:
500 10 ABAAABBBAABBABABAABAABABBBAABABABBAABABAABAABABABBBBABAABBAAAAAAABAABAABAABBABBABABBBABABBAABABBBBAABBBBABAAAAAAABAABAAABABABBAABABBABBAAAABAABBBAABABBABABBBBAAAABABBAAAAABAABBBBBBBBABBABBBAABBABBAAAABAABBBBBBAABBBAAAABABBAAABAABAABBBBAABBAAABBAABBAAAAABAAAAAABBAABABBABABBBABAAABBBAAABABAAABB...
output:
9129
result:
ok 1 number(s): "9129"
Test #21:
score: 0
Accepted
time: 4ms
memory: 3828kb
input:
500 500 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 4ms
memory: 3684kb
input:
500 416 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
84
result:
ok 1 number(s): "84"
Test #23:
score: 0
Accepted
time: 4ms
memory: 3636kb
input:
499 167 ABAABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB...
output:
2
result:
ok 1 number(s): "2"
Test #24:
score: 0
Accepted
time: 4ms
memory: 3856kb
input:
499 167 ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAA...
output:
2
result:
ok 1 number(s): "2"
Subtask #3:
score: 21
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #25:
score: 21
Accepted
time: 342ms
memory: 3756kb
input:
4918 2048 ABBBBBBAAAAABBBBAAAABBABBAAAABBBAABBBABABBAAAABBBAAAABAABBAAABAAABAABBAAABAAABBBAABBBBBBABAABBBBAAAAABBBBBABBBABABBBBBABAAAAAABAABBABBABBBBBAABAABAAAAAABBBBBAABBBABBBAAABBABBABBBAABBBBBBABBBABAABABABABABAAABBABABBAABAABBBBABABBAABABABABBAABABABBABABABAAABABBBABBBABBABBBBAAAABBBBAAABBBABBBA...
output:
138308
result:
ok 1 number(s): "138308"
Test #26:
score: 0
Accepted
time: 341ms
memory: 3700kb
input:
5000 4332 AABBBABBBABBBABBAABABABAAAABAAABBABABBBABBBBBABABAAAAABAAAAAAABBBBABBBABABABBABAABAABBBBABBABBBAABABABBAABBAABABAAABBBABABBABBBBBABBAAABBABBAAAABAAABBBAAABBAABBABAAABABAABBAAABBABABABAAABBBAAAABAAAABAABBAABBAAABBABAAABBABAABBBABABBBBABBBAAABBBABBABBABBABBAAABABAAAAAAABABBBAAABABBBAABBAABAA...
output:
999
result:
ok 1 number(s): "999"
Test #27:
score: 0
Accepted
time: 343ms
memory: 3800kb
input:
5000 1029 AAAAAAABAABBBAAABBBAABBABAABBBABBBBABAABAABBBBABAAAABBBAAAABBABABABABBBAAABAAABABBAAABAABAABAAAAAABAAABBBABBBABBBABBABAAAAAABBABABBBAAAAABBBAAAAAAAABBAABABAABBBAAAABBBBABBABBBAABBAAABBBBABAABABBBBBABBBAAAABAABBAAABBAAABAAAAAABAAABABBBAAAAABBBAAABBBAAAAABBABBABBBAAABAABABBBABBABBAABABBAAABA...
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 296ms
memory: 3932kb
input:
5000 1 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
25000000
result:
ok 1 number(s): "25000000"
Test #29:
score: 0
Accepted
time: 313ms
memory: 3884kb
input:
5000 2 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
18750000
result:
ok 1 number(s): "18750000"
Test #30:
score: 0
Accepted
time: 366ms
memory: 3936kb
input:
5000 4999 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
12502501
result:
ok 1 number(s): "12502501"
Test #31:
score: 0
Accepted
time: 339ms
memory: 3808kb
input:
5000 5000 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
12502500
result:
ok 1 number(s): "12502500"
Test #32:
score: 0
Accepted
time: 341ms
memory: 3888kb
input:
5000 10 ABABAABBAAAABAABBABBBBABAAABBBAAABAABAAABAAABAAABBBBBBBAAAABAABAABAAABBBAAABAAABABABABBABBAABABBABBAAAAABABABABAAABBBBABAABBABBBABBAABAABBBAAAAABBBAABABABBAAABBAAABAABAAABABAAABAAABAABAAAAABBBBBBBAABABAABBBBAABBAABAABABAAAABBBBBAABBBBBABAABAABABABAAAAABBBAAAABAABABBBABBAABABABAAAABAABBBAAAAB...
output:
1155101
result:
ok 1 number(s): "1155101"
Test #33:
score: 0
Accepted
time: 349ms
memory: 3940kb
input:
5000 1000 AABABBABABAAAABABABBABBABAAABABBABABAABBAABABBBBAABBABABABABAABBABABAAAABBBAAABBAABABBABBBAABBAAABABBAABABABBAABAABABBAABABBBBABAABAABABBBAAABBBABABABAABBAAAABBAABBAABBABABBBABABAABBAAAABBBAABABABBBABABAAABBABBAAAABABABABBABBBABABAAAABABBBAABABBBABABABABABAAABBBAABABBABABABABABAAAABABABABA...
output:
4212
result:
ok 1 number(s): "4212"
Test #34:
score: 0
Accepted
time: 357ms
memory: 3700kb
input:
5000 4138 ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
862
result:
ok 1 number(s): "862"
Test #35:
score: 0
Accepted
time: 354ms
memory: 3712kb
input:
5000 2379 ABAABABABABBABABAABABBABABAABABBAABBABABAABABABBAABABABABBABABAABABBAABBABABAABBABAABABABABBABABAABBABABABABAABABABBAABABABABBAABABBAABBABAABABABABBABAABABBAABBAABBABAABABABBABABAABABBAABBABABABAABBABABABAABBABABAABABABABBABABAABABABBABAABBAABABBABAABABBABABAABBABABABABABAABABBABABAABBAABB...
output:
1071
result:
ok 1 number(s): "1071"
Test #36:
score: 0
Accepted
time: 351ms
memory: 3700kb
input:
4999 1667 ABAABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAA...
output:
2
result:
ok 1 number(s): "2"
Test #37:
score: 0
Accepted
time: 360ms
memory: 3712kb
input:
4999 1667 ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB...
output:
2
result:
ok 1 number(s): "2"
Test #38:
score: 0
Accepted
time: 328ms
memory: 3756kb
input:
5000 1665 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
1388613
result:
ok 1 number(s): "1388613"
Subtask #4:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #39:
score: 0
Runtime Error
input:
59936 57569 BAAABBAAABBBABABAABABBAAABABABBABBAABABBBABBABABBBABABAABBBBAABABABAABAAAAAABABAAABBBBBABAAAABAAAABBAAABAAAAAABBAABAAABABAAABAABBABBBBBBABBBBABBAABBBABBBABAABAABAAABABBBBAAABAAAAAAABBABBAABABABBBAAABABBAABABBABAAAABABBBABABAAAABBABBBBBBAABBBBABBABBBAAAABAAAAAABBAAAABBBBBBBBAABBBBABABABBA...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%