Submission #338054


Source Code Expand

#include<iostream>
#include<stdio.h>
using namespace std;

int n, x;
char s[255];
long long dp[255][255][255];	//dp[文字数][スコア][にこ長さ]

int main() {
	int i, j, k, l;
	cin >> n >> x;
	cin >> s;
	
	dp[0][0][0] = 1;
	for( i = 0; i < n; i++ ) {
		for( j = 0; j <= x; j++ ) {
			for( k = 0; k <= n; k++ ) {
				if (dp[i][j][k] == 0) continue;
				dp[i][j][k] %= 1000000007;
				if ( s[i] != '?' ) {
					int t = s[i] - '0';
					if ( k % 2 ) {
						if ( t == 5 ) {
							dp[i+1][min(j + (k+1)/2, x)][k+1] += dp[i][j][k];
						}
						else {
							if ( t == 2 ) {
								dp[i+1][j][1] += dp[i][j][k];
							}
							else {
								dp[i+1][j][0] += dp[i][j][k];
							}
						}
					}
					else {
						if ( t == 2 ) {
							dp[i+1][j][k+1] += dp[i][j][k];
						}
						else {
							dp[i+1][j][0] += dp[i][j][k];
						}
					}
				}
				else {
					for( l = 0; l < 10; l++ ) {
						if ( k % 2 ) {
							if ( l == 5 ) {
								dp[i+1][min(j + (k+1)/2, x)][k+1] += dp[i][j][k];
							}
							else {
								if ( l == 2 ) {
									dp[i+1][j][1] += dp[i][j][k];
								}
								else {
									dp[i+1][j][0] += dp[i][j][k];
								}
							}
						}
						else {
							if ( l == 2 ) {
								dp[i+1][j][k+1] += dp[i][j][k];
							}
							else {
								dp[i+1][j][0] += dp[i][j][k];
							}
						}
					}
				}
			}
		}
	}
	
	long long ans = 0;
	for( i = 0; i <= n; i++ ) {
		ans += dp[n][x][i];
		ans %= 1000000007;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User startcpp
Language C++ (G++ 4.6.4)
Score 20
Code Size 1566 Byte
Status AC
Exec Time 283 ms
Memory 111544 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 20 / 20
Status
AC × 2
AC × 22
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 28 ms 1000 KB
sample_02.txt AC 26 ms 1080 KB
subtask1_01.txt AC 26 ms 1040 KB
subtask1_02.txt AC 26 ms 944 KB
subtask1_03.txt AC 28 ms 948 KB
subtask1_04.txt AC 27 ms 1004 KB
subtask1_05.txt AC 31 ms 2404 KB
subtask1_06.txt AC 54 ms 10164 KB
subtask1_07.txt AC 37 ms 2520 KB
subtask1_08.txt AC 66 ms 15332 KB
subtask1_09.txt AC 42 ms 7140 KB
subtask1_10.txt AC 33 ms 3600 KB
subtask1_11.txt AC 40 ms 5808 KB
subtask1_12.txt AC 155 ms 12344 KB
subtask1_13.txt AC 37 ms 3312 KB
subtask1_14.txt AC 176 ms 34744 KB
subtask1_15.txt AC 213 ms 73784 KB
subtask1_16.txt AC 208 ms 69172 KB
subtask1_17.txt AC 283 ms 111544 KB
subtask1_18.txt AC 145 ms 1972 KB
subtask1_19.txt AC 273 ms 111412 KB
subtask1_20.txt AC 207 ms 68148 KB
subtask1_21.txt AC 35 ms 2144 KB
subtask1_22.txt AC 31 ms 2132 KB