Submission #559225


Source Code Expand

import sys

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(N):
			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(N):
				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(N):
				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(N):
				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):
	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 1371 Byte
Status WA
Exec Time 2066 ms
Memory 143860 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 2
AC × 7
WA × 7
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 AC 62 ms 3712 KB
sample_02.txt AC 62 ms 3836 KB
subtask1_01.txt AC 60 ms 3656 KB
subtask1_02.txt WA 60 ms 3644 KB
subtask1_03.txt AC 62 ms 3668 KB
subtask1_04.txt WA 61 ms 3656 KB
subtask1_05.txt AC 261 ms 8832 KB
subtask1_06.txt AC 1207 ms 16840 KB
subtask1_07.txt WA 495 ms 9980 KB
subtask1_08.txt WA 1236 ms 15156 KB
subtask1_09.txt AC 427 ms 7548 KB
subtask1_10.txt WA 152 ms 4660 KB
subtask1_11.txt AC 749 ms 17876 KB
subtask1_12.txt TLE 2062 ms 141904 KB
subtask1_13.txt AC 794 ms 17848 KB
subtask1_14.txt TLE 2060 ms 143812 KB
subtask1_15.txt TLE 2064 ms 142200 KB
subtask1_16.txt TLE 2061 ms 141828 KB
subtask1_17.txt TLE 2062 ms 142716 KB
subtask1_18.txt TLE 2066 ms 142272 KB
subtask1_19.txt TLE 2062 ms 143800 KB
subtask1_20.txt TLE 2062 ms 143860 KB
subtask1_21.txt WA 271 ms 13884 KB
subtask1_22.txt WA 213 ms 11840 KB