dwangoプログラミングコンテスト

Submission #559529

Source codeソースコード

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 + 1):
			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 + 1):
				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 + 1):
				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 + 1):
				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

Task問題 A - ニコニコ文字列2
User nameユーザ名 bbb
Created time投稿日時
Language言語 Python (2.7.3)
Status状態 TLE
Score得点 0
Source lengthソースコード長 1431 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 0 / 20 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 61 ms 3668 KB
sample_02.txt AC 60 ms 3688 KB
subtask1_01.txt AC 58 ms 3688 KB
subtask1_02.txt AC 59 ms 3672 KB
subtask1_03.txt AC 57 ms 3668 KB
subtask1_04.txt AC 58 ms 3672 KB
subtask1_05.txt AC 193 ms 8816 KB
subtask1_06.txt AC 751 ms 16752 KB
subtask1_07.txt AC 333 ms 9960 KB
subtask1_08.txt AC 749 ms 15084 KB
subtask1_09.txt AC 277 ms 7540 KB
subtask1_10.txt AC 112 ms 4716 KB
subtask1_11.txt AC 508 ms 17868 KB
subtask1_12.txt TLE
subtask1_13.txt AC 522 ms 17828 KB
subtask1_14.txt TLE
subtask1_15.txt TLE
subtask1_16.txt TLE
subtask1_17.txt TLE
subtask1_18.txt TLE
subtask1_19.txt TLE
subtask1_20.txt TLE
subtask1_21.txt AC 207 ms 13872 KB
subtask1_22.txt AC 177 ms 11900 KB