Submission #559527


Source Code Expand

import sys
 
#sys.stdin = open('pro1_1.txt', 'r')
N , M = map(int, raw_input().split())
table = [[[0 for x in range(M + 1)] for x in range(N + 1)] for x in range(N + 1)]
s = list(raw_input())
ans = 0
 
def dp(i):
	if s[i] == '?':
		for x in range(i):
			for y in range(M + 1):
				if x % 2 == 1:
					table[i + 1][1][y] += table[i][x][y]
					if y + (x + 1) / 2 > M:
						table[i + 1][x + 1][M] += table[i][x][y]
					else:
						table[i + 1][x + 1][y + (x + 1) /2] += table[i][x][y]
					table[i + 1][0][y] += table[i][x][y] * 8
				else:
					table[i + 1][x + 1][y] += table[i][x][y]
					table[i + 1][0][y] += table[i][x][y] * 9
	else:
		if s[i] == '2':
			for x in range(i):
				for y in range(M + 1):
					if x % 2 == 0:
						table[i + 1][x + 1][y] += table[i][x][y]
					else:
						table[i + 1][1][y] += table[i][x][y]
		elif s[i] == '5':
			for x in range(i):
				for y in range(M + 1):
					if x % 2 == 1:
						if y + (x + 1) / 2 > M:
							table[i + 1][x + 1][M] += table[i][x][y]
						else:
							table[i + 1][x + 1][y + (x + 1) / 2] += table[i][x][y]
					else:
						table[i + 1][0][y] += table[i][x][y]
		else:
			for x in range(i):
				for y in range(M + 1):
					table[i + 1][0][y] += table[i][x][y]
table[0][0][0] = 1
for x in range(N):
	dp(x)
 
for x in range(N+1):
	ans += table[N][x][M]
 
mod = 1000000007
ans = ans % mod
print str(ans)

Submission Info

Submission Time
Task A - ニコニコ文字列2
User banban
Language Python (2.7.3)
Score 0
Code Size 1415 Byte
Status WA
Exec Time 2054 ms
Memory 143920 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
WA × 2
AC × 3
WA × 11
TLE × 8
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
sample_01.txt WA 64 ms 3696 KB
sample_02.txt WA 57 ms 3764 KB
subtask1_01.txt AC 59 ms 3768 KB
subtask1_02.txt WA 58 ms 3756 KB
subtask1_03.txt AC 58 ms 3668 KB
subtask1_04.txt WA 58 ms 3764 KB
subtask1_05.txt WA 189 ms 8884 KB
subtask1_06.txt AC 720 ms 16592 KB
subtask1_07.txt WA 316 ms 9916 KB
subtask1_08.txt WA 660 ms 11596 KB
subtask1_09.txt WA 246 ms 6704 KB
subtask1_10.txt WA 106 ms 4556 KB
subtask1_11.txt WA 454 ms 17872 KB
subtask1_12.txt TLE 2052 ms 138412 KB
subtask1_13.txt WA 494 ms 17872 KB
subtask1_14.txt TLE 2053 ms 143792 KB
subtask1_15.txt TLE 2052 ms 143816 KB
subtask1_16.txt TLE 2053 ms 142540 KB
subtask1_17.txt TLE 2054 ms 143800 KB
subtask1_18.txt TLE 2052 ms 143920 KB
subtask1_19.txt TLE 2052 ms 143820 KB
subtask1_20.txt TLE 2053 ms 143920 KB
subtask1_21.txt WA 181 ms 11692 KB
subtask1_22.txt WA 168 ms 11736 KB