QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132584#6338. Choruszhouhuanyi87 3271ms82636kbC++232.3kb2023-07-30 17:26:122023-07-30 17:26:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-30 17:26:15]
  • 评测
  • 测评结果:87
  • 用时:3271ms
  • 内存:82636kb
  • [2023-07-30 17:26:12]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#define N 2000000
#define inf 1e12
#define INF 2e18
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int l,r,ps;
};
reads dque[N+1];
int n,k,top,lg[N+1],s[N+1],cnt[N+1],pst[N+1],pst2[N+1];
long long sx,S[N+1],S2[N+1],ds[N+1],dp[N+1];
char c[N+1];
long long F(int l,int r)
{
	if (l>r) return INF;
	int sl=(l-1)<<1,sr=r<<1,mid=(sl+sr)>>1;
	long long res=0;
	if (pst[sl]==-1||pst[sl]<sl||pst[sl]>mid)
	{
		if (s[sl]<=0) res+=S2[mid-sl]-(ds[mid]-ds[sl]);
	}
	else res+=(S2[mid-sl]-S2[pst[sl]-sl])-(ds[mid]-ds[pst[sl]]);
	if (pst2[sr]==-1||pst2[sr]<mid||pst2[sr]>sr)
	{
		if (s[sr]<=0) res+=S[sr-mid]-(ds[sr]-ds[mid]);
	}
	else res+=(S[sr-mid]-S[sr-pst2[sr]])-(ds[pst2[sr]]-ds[mid]);
	return (res>>1)+sx;
}
long long calc(long long x)
{
	int d;
	for (int i=1;i<=n;++i) dp[i]=INF;
	sx=x,dque[top=1]=(reads){1,n,0};
	for (int i=1;i<=n;++i)
	{
		d=0;
		for (int j=lg[top];j>=0;--j)
			if (d+(1<<j)<=top&&dque[d+(1<<j)].l<=i)
				d+=(1<<j);
		cnt[i]=cnt[dque[d].ps]+1,dp[i]=dp[dque[d].ps]+F(dque[d].ps+1,i);
		while (top&&dp[i]+F(i+1,dque[top].l)<=dp[dque[top].ps]+F(dque[top].ps+1,dque[top].l)) top--;
		if (top&&dp[i]+F(i+1,dque[top].r)<=dp[dque[top].ps]+F(dque[top].ps+1,dque[top].r))
		{
			d=dque[top].r;
			for (int j=lg[dque[top].r-dque[top].l];j>=0;--j)
				if (d-(1<<j)>=dque[top].l&&dp[i]+F(i+1,d-(1<<j))<=dp[dque[top].ps]+F(dque[top].ps+1,d-(1<<j)))
					d-=(1<<j);
			dque[top].r=d-1;
		}
		d=dque[top].r+1;
		if (d<=n) dque[++top]=(reads){d,n,i};
	}
	return cnt[n];
}
int main()
{
	long long x=0;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=read(),k=read();
	for (int i=1;i<=(n<<1);++i)
	{
		cin>>c[i],S[i]=S[i-1]+i-1,S2[i]=S2[i-1]+i;
		if (c[i]=='A') s[i]=s[i-1]+1;
		else s[i]=s[i-1]-1;
		ds[i]=ds[i-1]+s[i];
	}
	for (int i=0;i<=(n<<1);++i) pst[i]=pst2[i]=-1;
	for (int i=0;i<=(n<<1);++i)
	{
		if (i-s[i]<=(n<<1)&&pst[i-s[i]]==-1) pst[i-s[i]]=i;
		if (i+s[i]<=(n<<1)&&pst2[i+s[i]]==-1) pst2[i+s[i]]=i;
	}
	for (int i=log(inf)/log(2);i>=0;--i)
		if (x+(1ll<<i)<=inf&&calc(x+(1ll<<i))>=k)
			x+=(1ll<<i);
	calc(x),printf("%lld\n",dp[n]-k*x);
	return 0;
}

详细

Subtask #1:

score: 16
Accepted

Test #1:

score: 16
Accepted
time: 5ms
memory: 19568kb

input:

1 1
BA

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 5ms
memory: 19360kb

input:

7 5
ABBAAABBABABBA

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 4ms
memory: 18564kb

input:

10 3
BABBABAABAABBABBBAAA

output:

26

result:

ok 1 number(s): "26"

Test #4:

score: 0
Accepted
time: 4ms
memory: 18260kb

input:

10 2
AAABBABABBAAABBBAABB

output:

11

result:

ok 1 number(s): "11"

Test #5:

score: 0
Accepted
time: 4ms
memory: 16408kb

input:

10 1
BBBBBBBBBBAAAAAAAAAA

output:

100

result:

ok 1 number(s): "100"

Test #6:

score: 0
Accepted
time: 5ms
memory: 19596kb

input:

10 2
BBBBBBBBBBAAAAAAAAAA

output:

75

result:

ok 1 number(s): "75"

Test #7:

score: 0
Accepted
time: 1ms
memory: 18168kb

input:

10 9
BBBBBBBBBBAAAAAAAAAA

output:

56

result:

ok 1 number(s): "56"

Test #8:

score: 0
Accepted
time: 3ms
memory: 18272kb

input:

10 10
BBBBBBBBBBAAAAAAAAAA

output:

55

result:

ok 1 number(s): "55"

Test #9:

score: 0
Accepted
time: 1ms
memory: 19380kb

input:

10 10
ABABABABABABABABABAB

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 4ms
memory: 19252kb

input:

10 2
ABAAABABABBBABABABAB

output:

14

result:

ok 1 number(s): "14"

Test #11:

score: 0
Accepted
time: 0ms
memory: 18168kb

input:

10 4
ABAABBAAABBBAAABBBAB

output:

2

result:

ok 1 number(s): "2"

Test #12:

score: 0
Accepted
time: 1ms
memory: 18648kb

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: 4ms
memory: 17804kb

input:

179 54
AAABABABABBAAABBABBABBABBBAAABAAAAABBBABAAAAABABBBAABBBABABBAABABAABABBBBABAABAABABABBBABBAABABBAABBAABABBAAABAAAAAAAABBAAAAABAAABBBBBBBABBAABBBABABAABBAABBABABABBABAAABABAAABABABBAABABAAABBABABABABABBAAABABBBBBBBAABBBAABABBBBABAABBAAAABAABBABABAABAAABABAAAABBBAABAAABBABABBBABAAABAABBBABBBBBA...

output:

41

result:

ok 1 number(s): "41"

Test #14:

score: 0
Accepted
time: 3ms
memory: 18584kb

input:

500 93
ABABAABBBBABAABAABAAAAABABBBBBABABBABAAAABAABBBBABAABBBAAABBABABAAAABAABBABAAABBAAABBBABBAAAAAABABABBBABABBBAABAAABAABABAAABAAABBAAABABBBAABBABBBABBBAABAAAABBBAABBBABAAAAAABABABBBABAAAABBBBBAABBBABAAABAABBBABABAABABBBBABBABBBBBBBABAAAABAABAABBABBBAABBBAAAAAAABBAABAAABBBABBBAAABABBBBAABBBABABB...

output:

235

result:

ok 1 number(s): "235"

Test #15:

score: 0
Accepted
time: 6ms
memory: 18276kb

input:

500 273
AAABBABAABAAABABAABBBABAAAABBAAABBABAAABBABABAAAABBBAAABBBAABAABAABBABABABABBAAABBBBBBBAABABBAABABBBAABBBBAAABAAAABABBABBBBBAABAABABAAAABBABABABAAAABBBAAAAABABBAABABABAAABBABAAAABABBBAAABABAABBAABBBAABAABBBAABABBBBABAAABAABBBBABBABAAABABBAABABBABBBBBBBABAABAAAABABABAAABABABABAABBAABBBABBBAAB...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 5ms
memory: 18244kb

input:

500 1
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

250000

result:

ok 1 number(s): "250000"

Test #17:

score: 0
Accepted
time: 5ms
memory: 16456kb

input:

500 2
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

187500

result:

ok 1 number(s): "187500"

Test #18:

score: 0
Accepted
time: 3ms
memory: 18136kb

input:

500 499
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

125251

result:

ok 1 number(s): "125251"

Test #19:

score: 0
Accepted
time: 3ms
memory: 19564kb

input:

500 500
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

125250

result:

ok 1 number(s): "125250"

Test #20:

score: 0
Accepted
time: 1ms
memory: 18396kb

input:

500 10
ABAAABBBAABBABABAABAABABBBAABABABBAABABAABAABABABBBBABAABBAAAAAAABAABAABAABBABBABABBBABABBAABABBBBAABBBBABAAAAAAABAABAAABABABBAABABBABBAAAABAABBBAABABBABABBBBAAAABABBAAAAABAABBBBBBBBABBABBBAABBABBAAAABAABBBBBBAABBBAAAABABBAAABAABAABBBBAABBAAABBAABBAAAAABAAAAAABBAABABBABABBBABAAABBBAAABABAAABB...

output:

9129

result:

ok 1 number(s): "9129"

Test #21:

score: 0
Accepted
time: 0ms
memory: 18440kb

input:

500 500
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

0

result:

ok 1 number(s): "0"

Test #22:

score: 0
Accepted
time: 3ms
memory: 18680kb

input:

500 416
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

84

result:

ok 1 number(s): "84"

Test #23:

score: 0
Accepted
time: 3ms
memory: 18788kb

input:

499 167
ABAABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB...

output:

2

result:

ok 1 number(s): "2"

Test #24:

score: 0
Accepted
time: 1ms
memory: 18896kb

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: 18ms
memory: 18312kb

input:

4918 2048
ABBBBBBAAAAABBBBAAAABBABBAAAABBBAABBBABABBAAAABBBAAAABAABBAAABAAABAABBAAABAAABBBAABBBBBBABAABBBBAAAAABBBBBABBBABABBBBBABAAAAAABAABBABBABBBBBAABAABAAAAAABBBBBAABBBABBBAAABBABBABBBAABBBBBBABBBABAABABABABABAAABBABABBAABAABBBBABABBAABABABABBAABABABBABABABAAABABBBABBBABBABBBBAAAABBBBAAABBBABBBA...

output:

138308

result:

ok 1 number(s): "138308"

Test #26:

score: 0
Accepted
time: 19ms
memory: 20572kb

input:

5000 4332
AABBBABBBABBBABBAABABABAAAABAAABBABABBBABBBBBABABAAAAABAAAAAAABBBBABBBABABABBABAABAABBBBABBABBBAABABABBAABBAABABAAABBBABABBABBBBBABBAAABBABBAAAABAAABBBAAABBAABBABAAABABAABBAAABBABABABAAABBBAAAABAAAABAABBAABBAAABBABAAABBABAABBBABABBBBABBBAAABBBABBABBABBABBAAABABAAAAAAABABBBAAABABBBAABBAABAA...

output:

999

result:

ok 1 number(s): "999"

Test #27:

score: 0
Accepted
time: 13ms
memory: 20160kb

input:

5000 1029
AAAAAAABAABBBAAABBBAABBABAABBBABBBBABAABAABBBBABAAAABBBAAAABBABABABABBBAAABAAABABBAAABAABAABAAAAAABAAABBBABBBABBBABBABAAAAAABBABABBBAAAAABBBAAAAAAAABBAABABAABBBAAAABBBBABBABBBAABBAAABBBBABAABABBBBBABBBAAAABAABBAAABBAAABAAAAAABAAABABBBAAAAABBBAAABBBAAAAABBABBABBBAAABAABABBBABBABBAABABBAAABA...

output:

0

result:

ok 1 number(s): "0"

Test #28:

score: 0
Accepted
time: 1ms
memory: 22040kb

input:

5000 1
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

25000000

result:

ok 1 number(s): "25000000"

Test #29:

score: 0
Accepted
time: 11ms
memory: 19688kb

input:

5000 2
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

18750000

result:

ok 1 number(s): "18750000"

Test #30:

score: 0
Accepted
time: 16ms
memory: 18648kb

input:

5000 4999
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

12502501

result:

ok 1 number(s): "12502501"

Test #31:

score: 0
Accepted
time: 17ms
memory: 19616kb

input:

5000 5000
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

12502500

result:

ok 1 number(s): "12502500"

Test #32:

score: 0
Accepted
time: 12ms
memory: 19064kb

input:

5000 10
ABABAABBAAAABAABBABBBBABAAABBBAAABAABAAABAAABAAABBBBBBBAAAABAABAABAAABBBAAABAAABABABABBABBAABABBABBAAAAABABABABAAABBBBABAABBABBBABBAABAABBBAAAAABBBAABABABBAAABBAAABAABAAABABAAABAAABAABAAAAABBBBBBBAABABAABBBBAABBAABAABABAAAABBBBBAABBBBBABAABAABABABAAAAABBBAAAABAABABBBABBAABABABAAAABAABBBAAAAB...

output:

1155101

result:

ok 1 number(s): "1155101"

Test #33:

score: 0
Accepted
time: 17ms
memory: 19100kb

input:

5000 1000
AABABBABABAAAABABABBABBABAAABABBABABAABBAABABBBBAABBABABABABAABBABABAAAABBBAAABBAABABBABBBAABBAAABABBAABABABBAABAABABBAABABBBBABAABAABABBBAAABBBABABABAABBAAAABBAABBAABBABABBBABABAABBAAAABBBAABABABBBABABAAABBABBAAAABABABABBABBBABABAAAABABBBAABABBBABABABABABAAABBBAABABBABABABABABAAAABABABABA...

output:

4212

result:

ok 1 number(s): "4212"

Test #34:

score: 0
Accepted
time: 19ms
memory: 20500kb

input:

5000 4138
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

862

result:

ok 1 number(s): "862"

Test #35:

score: 0
Accepted
time: 21ms
memory: 18660kb

input:

5000 2379
ABAABABABABBABABAABABBABABAABABBAABBABABAABABABBAABABABABBABABAABABBAABBABABAABBABAABABABABBABABAABBABABABABAABABABBAABABABABBAABABBAABBABAABABABABBABAABABBAABBAABBABAABABABBABABAABABBAABBABABABAABBABABABAABBABABAABABABABBABABAABABABBABAABBAABABBABAABABBABABAABBABABABABABAABABBABABAABBAABB...

output:

1071

result:

ok 1 number(s): "1071"

Test #36:

score: 0
Accepted
time: 18ms
memory: 19064kb

input:

4999 1667
ABAABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAA...

output:

2

result:

ok 1 number(s): "2"

Test #37:

score: 0
Accepted
time: 18ms
memory: 18180kb

input:

4999 1667
ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB...

output:

2

result:

ok 1 number(s): "2"

Test #38:

score: 0
Accepted
time: 10ms
memory: 18152kb

input:

5000 1665
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

1388613

result:

ok 1 number(s): "1388613"

Subtask #4:

score: 26
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #39:

score: 26
Accepted
time: 225ms
memory: 25228kb

input:

59936 57569
BAAABBAAABBBABABAABABBAAABABABBABBAABABBBABBABABBBABABAABBBBAABABABAABAAAAAABABAAABBBBBABAAAABAAAABBAAABAAAAAABBAABAAABABAAABAABBABBBBBBABBBBABBAABBBABBBABAABAABAAABABBBBAAABAAAAAAABBABBAABABABBBAAABABBAABABBABAAAABABBBABABAAAABBABBBBBBAABBBBABBABBBAAAABAAAAAABBAAAABBBBBBBBAABBBBABABABBA...

output:

33013

result:

ok 1 number(s): "33013"

Test #40:

score: 0
Accepted
time: 393ms
memory: 32816kb

input:

100000 8782
ABBABAAAABBBBBABAAABABAABBABABAABAABAABBABBAAAAAABBAAAABBBAAABBABAAAAAABBAABAABABAAAAABABAAABBBABBAABBABABBBABBAAAABBBBABABAAABAAAAAAABBBAABABBBBBABABBAABABAAABBBAAABABBBBBABBAAAAABAAAAAABBBAABAABBABABBAAAAAAABAABBBBAABBABABBAAABBAAABAABABBBABAABBAAABABABAABBBBABAAABABAAAABAAAABBBAABAAAA...

output:

198328

result:

ok 1 number(s): "198328"

Test #41:

score: 0
Accepted
time: 383ms
memory: 33700kb

input:

100000 38214
AAABBABBAABABAAABABAABBAABBBBAAAAAABAAABABAABABAAAAABABBBBABAAAAABBAAAABABAABBBAABAAABBAAABAAABBAABBBABABBBBABAABABAAABBAAABBBBAABABABBAAAABBABAAABBBBABBABABAABAAABBBAABBABABABBABBAAAABABBBBBBBBABBAABABBBBAABBBBAABBBAAAAAABAABABAABBAABAABAABBAABABAAAABAABABBABAABBBAAABAABAABAAABAABBAABA...

output:

0

result:

ok 1 number(s): "0"

Test #42:

score: 0
Accepted
time: 37ms
memory: 27796kb

input:

100000 1
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

10000000000

result:

ok 1 number(s): "10000000000"

Test #43:

score: 0
Accepted
time: 105ms
memory: 28052kb

input:

100000 2
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

7500000000

result:

ok 1 number(s): "7500000000"

Test #44:

score: 0
Accepted
time: 504ms
memory: 30164kb

input:

100000 99999
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

5000050001

result:

ok 1 number(s): "5000050001"

Test #45:

score: 0
Accepted
time: 507ms
memory: 29740kb

input:

100000 100000
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

output:

5000050000

result:

ok 1 number(s): "5000050000"

Test #46:

score: 0
Accepted
time: 459ms
memory: 34356kb

input:

100000 10
AABBABABAAABAABBAABBAABABABABBBBABAAAABAABAABBABBBABABBAABAABABBBABAABAAABABBBBAABBBAABAABBABBABAABABAAAABBBAAABBBABBBABAAAABBABAAAABAABBBBABBABBAABBBAAAABABBBABABAABABABABBAABBABAAABAAAAABABBBBBAAAABAABAAAABBABBABBAABABBBBBBABAABABBBABBBABAABBABABABAAAABABBBAAABBAABBBAABBBAAABBAAAABABBBBB...

output:

485360890

result:

ok 1 number(s): "485360890"

Test #47:

score: 0
Accepted
time: 436ms
memory: 32560kb

input:

100000 1000
ABAAAABBABAABBAAAAABBBABABAABAAAAAABABABABBAABBAAABAAABBAAABABBBBBABAABAAAABBBAABBBBBAAABAAAAAABABBBBAAAABBABBBABAABBAAABBABBBABBBBBABBBBBABAABABABBBBAABBABABABABAABABBAAAAAABABBBABBABBAAAABBBAAABBBBBBABAABBABAAAAABAABAAABBAABABAABBABAAAABABABABAAABBBBABAAAABAABABABBBABAABABABAAABAAABAAA...

output:

2235279

result:

ok 1 number(s): "2235279"

Test #48:

score: 0
Accepted
time: 564ms
memory: 29932kb

input:

100000 100000
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

0

result:

ok 1 number(s): "0"

Test #49:

score: 0
Accepted
time: 554ms
memory: 32284kb

input:

100000 76937
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA...

output:

23063

result:

ok 1 number(s): "23063"

Test #50:

score: 0
Accepted
time: 447ms
memory: 30844kb

input:

100000 12845
AABBABABABAAAAABBBABABABBAABAABABBBAAAABABAABAABBBBAAABBABBABBAAAABBBABABBBBABABAABBAAABABBAAABBBBAAAABBBAAABBBAAABABABABAABAABBABBABBAAAAABBBBBABBBABABAAAABABABAAAABBBBAAABAABABBBBBABBBAABAAAABABBBAAABBAAABAABABABABBBBBBBAABABBABABAABBABAAAABBBBAAABBBABAAABAAABBBBBAABBABABAABBAABBAABAA...

output:

118675

result:

ok 1 number(s): "118675"

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #51:

score: 13
Accepted
time: 3271ms
memory: 82636kb

input:

644992 518558
BBBAABABBAABBBABABBABABBABABAABABBAAABAAABABBBAABAABBAABAABABABAABAABABBBBBABBABABBABABBBBBBBBBBAABBBBBABBAABABBABBBABBBABBAAABABABAABBABABAABAAAAABABBBBBBABAABAAABBAAABBBBBAAABABAABABABAAAABAAABABABAABBABABBABAAABAAABBBABABAABBBAABABAABBBBABBBBABBAAAABBBAAAABAAAABBBBAAABBABBBBABABBBBA...

output:

141233

result:

ok 1 number(s): "141233"

Test #52:

score: -13
Time Limit Exceeded

input:

1000000 810099
AABBBABAAAABBBBBABABABAAABBBBABAABBBBBBBABAABBBBBAAABABABBBAAABBBBAABABABAAAABABABBABABABBABABABBAAABAAAAABBAABABABBAABBBBABBBABBAAAABBBBBAABAABBAAAAABBAABBBAAABAABAABAABAAABBBBABAABABAAAABBBBABBABBBABBBBABBAAABABAABABBBAABAAAABBBABABBABABBAABAABBBBBAABABABAABABABBBBBABABAAAAABBBBABAB...

output:


result: