Submission #559356


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(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+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 TLE
Exec Time 2059 ms
Memory 143748 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 20
Status
AC × 2
AC × 14
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 63 ms 3692 KB
sample_02.txt AC 60 ms 3568 KB
subtask1_01.txt AC 61 ms 3568 KB
subtask1_02.txt AC 55 ms 3572 KB
subtask1_03.txt AC 56 ms 3564 KB
subtask1_04.txt AC 57 ms 3568 KB
subtask1_05.txt AC 255 ms 8688 KB
subtask1_06.txt AC 1225 ms 16620 KB
subtask1_07.txt AC 508 ms 9840 KB
subtask1_08.txt AC 1267 ms 14956 KB
subtask1_09.txt AC 458 ms 7268 KB
subtask1_10.txt AC 148 ms 4588 KB
subtask1_11.txt AC 736 ms 17784 KB
subtask1_12.txt TLE 2053 ms 143748 KB
subtask1_13.txt AC 776 ms 17644 KB
subtask1_14.txt TLE 2054 ms 143720 KB
subtask1_15.txt TLE 2053 ms 141292 KB
subtask1_16.txt TLE 2056 ms 141920 KB
subtask1_17.txt TLE 2053 ms 140224 KB
subtask1_18.txt TLE 2052 ms 142576 KB
subtask1_19.txt TLE 2059 ms 141812 KB
subtask1_20.txt TLE 2054 ms 143224 KB
subtask1_21.txt AC 265 ms 13664 KB
subtask1_22.txt AC 207 ms 11760 KB