QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#687711#9463. 基础 ABC 练习题NKheyuxiang100 ✓2402ms7740kbC++141.4kb2024-10-29 20:41:072024-10-29 20:41:07

Judging History

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

  • [2024-10-29 20:41:07]
  • 评测
  • 测评结果:100
  • 用时:2402ms
  • 内存:7740kb
  • [2024-10-29 20:41:07]
  • 提交

answer

#include<bits/stdc++.h>
#define N 63
using namespace std;
int n;
signed int dp[N][N][N][2][2];
char s[N*3],t0[N],t1[N];
int nxt0[N],nxt1[N];
signed int DP(int x,int y,int z){
	for(int i=0;i<=n;i++)
		for(int j=0;j<=min(n,y+i);j++)
			for(int k=max(0,i-x);k<=min(n,z+j);k++){
				int p=i+j+k;
				if(p==0){
					dp[i][j][k][x==0][y==0]=1;
					continue;
				}
				for(int u=0;u<2;u++)
					for(int v=0;v<2;v++){
						int tu=u|(i-k==x),tv=v|(j-i==y);
						signed int &f=dp[i][j][k][tu][tv];
						if((s[p]=='?'||s[p]=='A')&&i>0)
							f+=dp[i-1][j][k][u][v];
						if((s[p]=='?'||s[p]=='B')&&j>0)
							f+=dp[i][j-1][k][u][v];
						if((s[p]=='?'||s[p]=='C')&&k>0)
							f+=dp[i][j][k-1][u][v];
					}
			}
	signed int res=dp[n][n][n][1][1];
	for(int i=0;i<=n;i++)
		for(int j=0;j<=min(n,y+i);j++)
			for(int k=max(0,i-x);k<=min(n,z+j);k++)
				for(int u=0;u<2;u++)
					for(int v=0;v<2;v++)
						dp[i][j][k][u][v]=0;
	return res;
}
int main(){
	int t,id;
	scanf("%d%d",&t,&id);
	for(int o=1;o<=t;o++){
		scanf("%d%s%s%s",&n,t0,t1,s+1);
		if(o<t) puts("-1");
	}
	nxt0[n+1]=nxt1[n+1]=n+1;
	for(int i=n;i>=0;i--){
		nxt0[i]=(t0[i]=='1'?i:nxt0[i+1]);
		nxt1[i]=(t1[i]=='1'?i:nxt1[i+1]);
	}
	signed int ans=0;
	for(int i=0;i<=n;i++)
		for(int j=0;i+j<=n;j++)
			if(nxt0[i]+nxt1[j]<=n)
				ans+=DP(i,j,n-nxt0[i]-nxt1[j]);
	printf("%u\n",ans);
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 1645ms
memory: 7736kb

input:

60 1
1
11
11
ABC
2
111
111
CABABC
3
1111
1111
CAABBCBAC
4
11111
11111
BACBBACBACAC
5
111111
111111
CABCCBBAABCCBAA
6
1111111
1111111
ABABABCACBCBCCACBA
7
11111111
11111111
BCAABACBBCBBABCCAACAC
8
111111111
111111111
CCBCBBBCAABCBCAAAAACBCBA
9
1111111111
1111111111
CCCCACABCBABAABCCAABABBCBBA
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #2:

score: 20
Accepted
time: 1636ms
memory: 7548kb

input:

60 1
1
11
11
CBA
2
111
111
BACACB
3
1111
1111
BCBCACABA
4
11111
11111
CCBACABBBCAA
5
111111
111111
BCACBBABBCCAACA
6
1111111
1111111
BBCBACCAACBCBCAABA
7
11111111
11111111
ACBCCBBAABAABCACCACBB
8
111111111
111111111
BAACACBACCCBAACCBABABBCB
9
1111111111
1111111111
BABCBCAAAAABBCCCACBCBBABACC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #3:

score: 20
Accepted
time: 1629ms
memory: 7692kb

input:

60 1
1
11
11
BCA
2
111
111
BCABCA
3
1111
1111
CBACCAABB
4
11111
11111
BACBCBBCCAAA
5
111111
111111
BCCCBABACCBABAA
6
1111111
1111111
ACAACBABABBCACBCCB
7
11111111
11111111
BBBCABCCCAABCACBACAAB
8
111111111
111111111
ACCACAABACBAABBCBCBBACBC
9
1111111111
1111111111
BCCBACBBACCCBCCAABAACABAABB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #4:

score: 20
Accepted
time: 1630ms
memory: 7604kb

input:

60 1
1
11
11
BCA
2
111
111
ACABCB
3
1111
1111
BABCABCCA
4
11111
11111
CCABACABBACB
5
111111
111111
ABBBCBBCACCAACA
6
1111111
1111111
CACBABCABCCBABAACB
7
11111111
11111111
BACBCABACBBCCCBAAACAB
8
111111111
111111111
CABABBCAACABCBACBABACBCC
9
1111111111
1111111111
BCBAACBABABCBACBABABCCACACC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #5:

score: 20
Accepted
time: 1638ms
memory: 7548kb

input:

60 1
1
11
11
ABC
2
111
111
BBCACA
3
1111
1111
ACBBCBAAC
4
11111
11111
ABACACCCABBB
5
111111
111111
ACCCCCAAABABBBB
6
1111111
1111111
ABAABBBBCCCCCCAABA
7
11111111
11111111
ACBBBACCCCCCAABABBBAA
8
111111111
111111111
CAAABAAACCCCBBCBBBCACBAB
9
1111111111
1111111111
ABAAACBBCCCCCCCBAAABAACBBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #6:

score: 20
Accepted
time: 1622ms
memory: 7548kb

input:

60 1
1
11
11
BCA
2
111
111
ACCBAB
3
1111
1111
BACCACBBA
4
11111
11111
AAABBCBCBACC
5
111111
111111
AABBBBCCBCCAACA
6
1111111
1111111
AAACCBCCCAABACBBBB
7
11111111
11111111
AAACACCACBBAABBCBCCBB
8
111111111
111111111
AAACAAABBBBBBBCBACCCACCC
9
1111111111
1111111111
BBCCACCCACCACCBAABBAAAABBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #7:

score: 20
Accepted
time: 1631ms
memory: 7552kb

input:

60 1
1
11
11
BCA
2
111
111
ACCABB
3
1111
1111
CAABBBCAC
4
11111
11111
BBCCBCCABAAA
5
111111
111111
BAABBBCCCCCAABA
6
1111111
1111111
AACACCCCBABBBCAABB
7
11111111
11111111
AACBBCBBBCCCCCAAABBAA
8
111111111
111111111
AAAABBCBBBBCBBCCCCCCAAAA
9
1111111111
1111111111
ABBBBBBBBCCBCAACCACAACCAAAC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #8:

score: 20
Accepted
time: 1641ms
memory: 7624kb

input:

60 1
1
11
11
ABC
2
111
111
AABCBC
3
1111
1111
ABAACBBCC
4
11111
11111
AABCCBBBCACA
5
111111
111111
AAACCABBBACBCCB
6
1111111
1111111
AABBBBBBCCACAACACC
7
11111111
11111111
AAAABBBBBBCCACCCCCBAA
8
111111111
111111111
ACCBABBABBBBBCCCACCCAAAA
9
1111111111
1111111111
BAAAABCCCCCCCBBAABAACABCBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #9:

score: 20
Accepted
time: 1635ms
memory: 7616kb

input:

60 1
1
11
11
CAB
2
111
111
CCAABB
3
1111
1111
ACCCABBAB
4
11111
11111
AAABBBBCCACC
5
111111
111111
BCACCCCBAAAABBB
6
1111111
1111111
CAAACABABACCCBCBBB
7
11111111
11111111
ACAAACBCCCCBCAABBABBB
8
111111111
111111111
ACCAACACCCCCABABAABBBBBB
9
1111111111
1111111111
AACAAAAAACBCCBCBACBBBBBBCCC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #10:

score: 20
Accepted
time: 1612ms
memory: 7736kb

input:

60 1
1
11
11
BCA
2
111
111
ACACBB
3
1111
1111
AABCCCABB
4
11111
11111
CBCCCABABABA
5
111111
111111
ACACCCAABBCBABB
6
1111111
1111111
BACAAAACCBABCBCBCB
7
11111111
11111111
AAAAABBBBCCBBCCCCACAB
8
111111111
111111111
AACCCCCCABAAACAABCBBBBBB
9
1111111111
1111111111
AABAAAABCCCCABCCCABBCCABBBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #11:

score: 20
Accepted
time: 1615ms
memory: 7608kb

input:

60 1
1
11
11
BCA
2
111
111
CBBCAA
3
1111
1111
AABABCCCB
4
11111
11111
BABCBBCAAACC
5
111111
111111
AAACBBBBBCAACCC
6
1111111
1111111
BBBBBCCCCCCAABAAAA
7
11111111
11111111
BAAAABAACCCABBCCBBBCC
8
111111111
111111111
ABABBBBBCBCCCACCCCAAABAA
9
1111111111
1111111111
AAAABBAABCABACCCACCCBBCBCBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #12:

score: 20
Accepted
time: 1503ms
memory: 7692kb

input:

60 2
1
01
11
ABC
2
101
001
ACBABC
3
0011
1000
AAACBBCBC
4
11100
00100
BACABCABACBC
5
001101
110010
ACBABCCABBCCAAB
6
0101010
1000011
CABBAAACACBBCCABCB
7
10010111
10100111
CABAAACBBAACBCACBBBCC
8
100101000
100000110
BACBCACBBAABCCCABCBAACBA
9
1100010100
0111110011
CAABCBBABCACBCACABCABAACBBC
10
0001...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #13:

score: 20
Accepted
time: 1489ms
memory: 7604kb

input:

60 2
1
01
01
CAB
2
011
101
ABCCBA
3
1111
0000
CBBAACCBA
4
00011
10011
BCCBCCABABAA
5
011111
111011
ACBBABCBCCAACBA
6
1011101
1101000
CBABBCACBAABABCACC
7
00001111
11010100
BCACAABCBBBCCABABCACA
8
110110100
010010100
ABAABCABCABAACCCCBBBBCCA
9
0000111111
1011100011
BAAABBCCABBBBCABACBACACCACC
10
0011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #14:

score: 20
Accepted
time: 1501ms
memory: 7672kb

input:

60 2
1
01
00
ABC
2
111
000
CAABBC
3
0101
0011
CAACBCBAB
4
11011
01001
CABBCAACBBCA
5
000010
010100
BCCCACAAACBBBBA
6
0011011
0011000
BCACCBAAAAABCBCBBC
7
11000001
11111111
AACBCABACCBBCABCCBAAB
8
111010100
111101010
CBABCACBABAACBABCCCBCAAB
9
1001111111
1011000111
CAABCACCABBBABBCACCABBCAACB
10
0011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #15:

score: 20
Accepted
time: 1504ms
memory: 7584kb

input:

60 2
1
00
10
BCA
2
110
000
BCAABC
3
0111
1001
CACAABBBC
4
10101
00000
ACCBCAABBACB
5
010001
100001
BBCBBAACCBACACA
6
0100101
0100010
CCAAAABCCAABBCBBBC
7
10010000
10010011
BCBCACBCBAAAABCABBCCA
8
001101111
110010111
CABACABCACBBABCBCABACABC
9
1000111100
1011101001
ACBCABABBCCBABCCAAACBBBACAC
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #16:

score: 20
Accepted
time: 337ms
memory: 6664kb

input:

60 2
1
10
11
CAB
2
110
100
AABBCC
3
0100
0110
CAABCBABC
4
01010
01000
BCBCABACBCAA
5
001110
100000
AAABBCCCABCBABC
6
1000000
1101100
ACCBACBCAABCAABBCB
7
11011110
01000000
AAAAABABBBCBBBACCCCCC
8
101000000
010000000
ACBABBCCCCCCCABAAABAABBB
9
1000000000
1000000000
CCCCCCCCCAABAAABABBBABBAABB
10
0111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #17:

score: 20
Accepted
time: 758ms
memory: 7000kb

input:

60 2
1
01
10
ABC
2
100
100
BCABCA
3
1000
1100
CABACCBAB
4
11001
10000
AABCBACABBCC
5
110000
101110
BACBCAABCABCBCA
6
1110000
1111100
AABBBBCABCCCCABAAC
7
10110000
11100000
AAACCABBCAABCBBABBCCC
8
001111100
011000000
ABAACAAAACABCBCBBBBBCCCC
9
0110000000
1111000000
AACBBACBBBCBCABACACBCAABCCA
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #18:

score: 20
Accepted
time: 14ms
memory: 5956kb

input:

60 2
1
10
11
ABC
2
100
100
CABCAB
3
1000
1000
CCABCABAB
4
11100
10000
ACACBABCABCB
5
111101
100000
AABCABCBACABBCC
6
1000000
0100000
BCACCCCCABAAABBBBA
7
10101110
11000000
AAABBCBBCACCCABBAACBC
8
111110000
001100000
ACBBCBBCABACCACBBABAACCA
9
1110000000
1111110000
CAAACBCCBBAAABCCBACABACCBBB
10
1100...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #19:

score: 20
Accepted
time: 28ms
memory: 6672kb

input:

60 2
1
11
10
ABC
2
100
110
BCABCA
3
1000
1111
BBCBACCAA
4
10000
10011
BCABCABCABCA
5
011111
100000
AABCBCABACABCBC
6
1110000
1000000
CAAACCCBBBCAACABBB
7
10000000
01000000
ABBCACCCABBACABACBBAC
8
110100011
100000000
AABBCABCCAABBCABCABCABCC
9
1111011100
1100000000
AAACABBBBBCACABCCBABCACBCCA
10
0111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Test #20:

score: 20
Accepted
time: 632ms
memory: 7492kb

input:

60 2
1
10
10
CAB
2
110
100
ABCACB
3
1000
1000
CABCABCAB
4
10111
10000
CABCABCABCAB
5
100000
110000
BCCAABCBCABACAB
6
1000000
1111000
CCCABACAABBCABCABB
7
10000000
11000110
BBCBBBCCACCCBABAAACAA
8
110000000
100000000
AACBCABCABBACCABCBCAABBC
9
1000000000
1100000000
BBCCACACCCBBACBCCABABAAAABB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0

result:

ok Accepted!!!

Test #21:

score: 20
Accepted
time: 30ms
memory: 6060kb

input:

60 2
1
10
10
CAB
2
110
100
CABCAB
3
0111
1000
CABCABCAB
4
11010
11000
AAABBBCBACCC
5
110000
100000
ACBACABCBABCABC
6
1111000
1111000
AAABBBBBCACCCAABCC
7
11011100
01000000
AAAAACCBCBCBBBCACACBB
8
111000000
111010000
AAABBBBBCCCCCCCABACABABA
9
1011100010
1000000000
AAABAABAABBABBCCCCBCCCCBACB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1

result:

ok Accepted!!!

Subtask #3:

score: 10
Accepted

Test #22:

score: 10
Accepted
time: 2273ms
memory: 7732kb

input:

60 3
1
11
11
???
2
111
111
??????
3
1111
1111
?????????
4
11111
11111
????????????
5
111111
111111
???????????????
6
1111111
1111111
??????????????????
7
11111111
11111111
?????????????????????
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
???????????????????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Subtask #4:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Test #23:

score: 20
Accepted
time: 1794ms
memory: 7556kb

input:

60 4
1
11
11
AC?
2
111
111
?ACAAA
3
1111
1111
AA?A?CCCC
4
11111
11111
??BBB?CBBACA
5
111111
111111
?CC?CCCAA?BCB??
6
1111111
1111111
?B?BBCCABBCBA?A?BC
7
11111111
11111111
AAA?B??C?CBABACCCA?AA
8
111111111
111111111
CBBB?AAC?B?A???BABAC?ACB
9
1111111111
1111111111
A?A?BAA?BCBC??ABBBBAAA?ACBB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
967466944

result:

ok Accepted!!!

Test #24:

score: 20
Accepted
time: 1764ms
memory: 7680kb

input:

60 4
1
11
11
CCA
2
111
111
BBAABC
3
1111
1111
?BACB?B?B
4
11111
11111
B??ACBBCBBA?
5
111111
111111
ABBBBC?CABCABA?
6
1111111
1111111
?ACAB?CAA?AB?C?AAC
7
11111111
11111111
?BAAA?BCAAA??AB?BABAC
8
111111111
111111111
BCBCC?ACACA?AAAC??BACACA
9
1111111111
1111111111
ACCCBCBAA?BABBA??BBBBACAA?A
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1537951906

result:

ok Accepted!!!

Test #25:

score: 20
Accepted
time: 1818ms
memory: 7612kb

input:

60 4
1
11
11
A?B
2
111
111
BABBBB
3
1111
1111
?ABBABBCC
4
11111
11111
CBABBBCBABAB
5
111111
111111
AABCBA?CBBCCBBA
6
1111111
1111111
AB????CCBCC?BCBBB?
7
11111111
11111111
C?BBBC?BABCC?CC?A?BAC
8
111111111
111111111
CCAAACA?C?A??AAAABC?CAC?
9
1111111111
1111111111
BAABBBCA?A?BA?CA??CAAABBBAB
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2235249070

result:

ok Accepted!!!

Test #26:

score: 20
Accepted
time: 2283ms
memory: 7688kb

input:

60 4
1
11
11
???
2
111
111
???C??
3
1111
1111
?????????
4
11111
11111
?C???????AAA
5
111111
111111
???????????????
6
1111111
1111111
?????B???C?A?B?BC?
7
11111111
11111111
??????B??????A????C??
8
111111111
111111111
???????????C?CB?????????
9
1111111111
1111111111
??????B??CC?????B??C???????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2776680263

result:

ok Accepted!!!

Test #27:

score: 20
Accepted
time: 2402ms
memory: 7556kb

input:

60 4
1
11
11
???
2
111
111
??????
3
1111
1111
?????????
4
11111
11111
???AC?????A?
5
111111
111111
????????C??A???
6
1111111
1111111
?A???????????????C
7
11111111
11111111
BC?C??????B??A?B?A???
8
111111111
111111111
???????C?????A??????????
9
1111111111
1111111111
???????????????????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
975867735

result:

ok Accepted!!!

Test #28:

score: 20
Accepted
time: 2343ms
memory: 7604kb

input:

60 4
1
11
11
???
2
111
111
?B????
3
1111
1111
???????B?
4
11111
11111
????????????
5
111111
111111
?C??????????AA?
6
1111111
1111111
?????????????????A
7
11111111
11111111
?AA??????AB?CBC??????
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
??A??????B?????A?????B????A
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3283652662

result:

ok Accepted!!!

Test #29:

score: 20
Accepted
time: 2253ms
memory: 7668kb

input:

60 4
1
11
11
B?A
2
111
111
BACA??
3
1111
1111
???B?AB??
4
11111
11111
?BC?????A?B?
5
111111
111111
??BA??A?B??????
6
1111111
1111111
??????????????????
7
11111111
11111111
B?C?A????C???C???????
8
111111111
111111111
???B????????????????????
9
1111111111
1111111111
A?????????????????????????A
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Test #30:

score: 20
Accepted
time: 2275ms
memory: 7676kb

input:

60 4
1
11
11
A?B
2
111
111
A?CBCA
3
1111
1111
?????????
4
11111
11111
C??C?????A??
5
111111
111111
???????A???????
6
1111111
1111111
?????????AC???C???
7
11111111
11111111
?????????????????A???
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
??????????????A????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
776867426

result:

ok Accepted!!!

Test #31:

score: 20
Accepted
time: 2299ms
memory: 7688kb

input:

60 4
1
11
11
?AA
2
111
111
A??BB?
3
1111
1111
??????B?C
4
11111
11111
????C???????
5
111111
111111
?B????B????????
6
1111111
1111111
?????????????A????
7
11111111
11111111
?B??A?????????A????BA
8
111111111
111111111
????????????????????????
9
1111111111
1111111111
??A????B?????AB???B????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Test #32:

score: 20
Accepted
time: 2261ms
memory: 7604kb

input:

60 4
1
11
11
A?C
2
111
111
?B?B??
3
1111
1111
?A????C??
4
11111
11111
???A????B???
5
111111
111111
??????C?A??B?B?
6
1111111
1111111
????C??????B?C??B?
7
11111111
11111111
???????????B????A????
8
111111111
111111111
??CAC????C??????????????
9
1111111111
1111111111
?????????C???????????????C?
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3736489762

result:

ok Accepted!!!

Subtask #5:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #33:

score: 30
Accepted
time: 1580ms
memory: 7616kb

input:

60 5
1
10
11
BBB
2
110
111
?BAAAC
3
0011
1010
A?AC?A?C?
4
00000
10100
CACBBC?AABBC
5
000011
010001
?CAACC?BBCBCBBB
6
0100111
0011111
C??BAC??ACCCAC?BB?
7
00010001
10011110
??BCABCB???CAAAABBCC?
8
100100000
111010111
?BCACCBACCCCACABAA?CACA?
9
1100111101
0010011010
?BCBCBCCAC?ACBBCBAB?ABBC?B?
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
981665096

result:

ok Accepted!!!

Test #34:

score: 30
Accepted
time: 1596ms
memory: 7684kb

input:

60 5
1
10
01
BC?
2
010
101
AA?CCB
3
1100
1011
CCACCAB?C
4
01011
00011
CBCCCCABCCCC
5
010110
111011
B?CB?AB?C?C?BCC
6
0100111
0011110
???C?AA?BBAB?CBABC
7
11100011
11000000
BCB?ACBBA?????BBBCA??
8
011000000
100101110
AB?ACCCBBBCCBBA?CAAA?AAB
9
0110101010
1001110110
BB?BBC?BAABA?AC?ABC???CCC??
10
0111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
927252812

result:

ok Accepted!!!

Test #35:

score: 30
Accepted
time: 1688ms
memory: 7668kb

input:

60 5
1
01
00
C?C
2
100
111
ACA?AC
3
0000
1001
CCABA?BAA
4
11011
01100
BBB??AA??BB?
5
100001
001111
CCBCAAC????ACB?
6
0010010
0010110
?BCB??CAAABAABBAC?
7
10001011
01011101
BBCACCCACBBC?CCCCB?CB
8
111100000
000000111
?AAC?B?A?BC?AA?A??A?CBA?
9
0000000101
0011011101
BB?BCABAC?ACA??ABCC?ACB????
10
1101...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
754781458

result:

ok Accepted!!!

Test #36:

score: 30
Accepted
time: 2266ms
memory: 7740kb

input:

60 5
1
11
11
??A
2
111
111
A????C
3
0111
1111
??B????C?
4
11111
11101
????????????
5
101111
111001
?B?B??????AC?C?
6
1111111
1111011
C???????B??CB?????
7
10111111
11111110
??????????????????BA?
8
111110100
011111011
????????????????????????
9
1100011111
1101011011
??AC????B??CB???C?C?????CC?
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
621310044

result:

ok Accepted!!!

Test #37:

score: 30
Accepted
time: 2286ms
memory: 7600kb

input:

60 5
1
11
11
?B?
2
110
110
??????
3
1111
1111
???????C?
4
11101
10111
????A????A??
5
110111
010111
?????A??????C?B
6
0111111
1011110
??BB?????????B????
7
11111100
01110111
????????A??A?B????C??
8
011101101
111100011
?B???????B?A?C???B??????
9
1111101111
1111101111
??BC?????C?A?????C???????BB
10
1010...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
522683520

result:

ok Accepted!!!

Test #38:

score: 30
Accepted
time: 2266ms
memory: 7668kb

input:

60 5
1
11
11
C??
2
111
101
??????
3
1111
1101
???C???C?
4
11110
11111
???????C????
5
011111
111101
????B????????B?
6
1011111
1111111
B????C?????AA????C
7
11110111
01111111
??????C??????????????
8
110111100
110011101
?????C????????????A?????
9
1110101111
1101111011
?????B????C???C???????CA???
10
1011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2768886394

result:

ok Accepted!!!

Test #39:

score: 30
Accepted
time: 2233ms
memory: 7592kb

input:

60 5
1
10
00
BAA
2
111
111
CBC??A
3
0000
0000
A??BA??BA
4
00100
11111
????????????
5
111111
000010
??A?????????AA?
6
0000110
0100010
B??????????C???C??
7
01011000
11111111
?????A???????????????
8
101000101
100111101
?B?????????????????A????
9
1011010011
1111111111
????????C??C?B????AC???????
10
1101...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2198024491

result:

ok Accepted!!!

Test #40:

score: 30
Accepted
time: 2265ms
memory: 7624kb

input:

60 5
1
00
00
CBA
2
111
111
BCB?CC
3
0110
1011
?A?B?B??C
4
10111
00000
????A????BB?
5
100000
111110
????????B??????
6
1011111
0100101
C????C??????ACA???
7
11111111
11111101
????????????????C????
8
101000101
110001010
??????????A???C??C?A????
9
1000101111
1111101111
????B?C??CC?????????????C??
10
1011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3444482677

result:

ok Accepted!!!

Test #41:

score: 30
Accepted
time: 2240ms
memory: 7672kb

input:

60 5
1
10
01
AAB
2
100
110
??????
3
1111
1111
?A?AB???C
4
01100
11110
BA?A?A??C???
5
110000
111101
?????????C?C?A?
6
0001010
0100011
A??B????????B???A?
7
00101010
11111111
????????????????????B
8
101111011
011111111
?B???????????C?????C?A??
9
1101110111
0111111111
?????C?????AB??????????A???
10
1011...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2103642368

result:

ok Accepted!!!

Test #42:

score: 30
Accepted
time: 2314ms
memory: 7688kb

input:

60 5
1
10
10
CCC
2
110
000
CA?CA?
3
0101
1100
BBBB??B??
4
10000
00000
C??????AA???
5
010100
000001
????C??B??C????
6
0011111
0110101
????????????A?A???
7
10111100
11111011
?????????????????????
8
010111001
110010010
???????????????B???A????
9
1111100111
1101111110
???????????????????????????
10
1111...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2853696586

result:

ok Accepted!!!

Extra Test:

score: 0
Extra Test Passed