Submission #338079


Source Code Expand

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int MOD = 1000000007;

int main(){
	int N, X;
	long long dp[2][300][300];
	while(cin >> N >> X){
		string s; cin >> s;
		memset(dp, 0, sizeof(dp));
		dp[0][0][0] = 1;
		for(int i=0;i<N;i++){
			int cur = i%2, next = 1-cur;
			memset(dp[next], 0, sizeof(dp[next]));
			for(int j=0;j<=i;j++){
				for(int k=0;k<=X;k++){
					if(s[i] == '?'){
						int add = 0;
						if((j+1)%2 == 0){
							add = (j+1)/2;
						}
						dp[next][j+1][min(X, k+add)] += dp[cur][j][k];
						dp[next][j+1][min(X, k+add)] %= MOD;
						if((j+1)%2 == 0){
							dp[next][0][k] += 8*dp[cur][j][k];
							dp[next][0][k] %= MOD;
							dp[next][1][k] += dp[cur][j][k];
							dp[next][1][k] %= MOD;
						} else {
							dp[next][0][k] += 9*dp[cur][j][k];
							dp[next][0][k] %= MOD;
						}
					} else {
						if((j%2 == 0 && s[i] == '2') || (j%2 == 1 && s[i] == '5')){
							int add = 0;
							if((j+1)%2 == 0){
								add = (j+1)/2;
							}
							dp[next][j+1][min(X, k+add)] += dp[cur][j][k];
							dp[next][j+1][min(X, k+add)] %= MOD;
						} else {
							if(j%2 == 1 && s[i] == '2'){
								dp[next][1][k] += dp[cur][j][k];
								dp[next][1][k] %= MOD;
							} else {
								dp[next][0][k] += dp[cur][j][k];
								dp[next][0][k] %= MOD;
							}
						}
					}
				}
			}
		}
		long long res = 0;
		for(int i=0;i<=N;i++){
			res += dp[N%2][i][X];
			res %= MOD;
		}
		cout << res << endl;
	}
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User pes
Language C++ (G++ 4.6.4)
Score 20
Code Size 1542 Byte
Status AC
Exec Time 165 ms
Memory 2328 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 27 ms 2168 KB
sample_02.txt AC 28 ms 2328 KB
subtask1_01.txt AC 27 ms 2208 KB
subtask1_02.txt AC 27 ms 2084 KB
subtask1_03.txt AC 26 ms 2088 KB
subtask1_04.txt AC 28 ms 2080 KB
subtask1_05.txt AC 40 ms 2204 KB
subtask1_06.txt AC 43 ms 2212 KB
subtask1_07.txt AC 39 ms 2204 KB
subtask1_08.txt AC 36 ms 2200 KB
subtask1_09.txt AC 34 ms 2084 KB
subtask1_10.txt AC 29 ms 2208 KB
subtask1_11.txt AC 46 ms 2208 KB
subtask1_12.txt AC 128 ms 2164 KB
subtask1_13.txt AC 46 ms 2084 KB
subtask1_14.txt AC 130 ms 2208 KB
subtask1_15.txt AC 120 ms 2208 KB
subtask1_16.txt AC 123 ms 2208 KB
subtask1_17.txt AC 165 ms 2088 KB
subtask1_18.txt AC 112 ms 2208 KB
subtask1_19.txt AC 163 ms 2096 KB
subtask1_20.txt AC 126 ms 2092 KB
subtask1_21.txt AC 43 ms 2204 KB
subtask1_22.txt AC 45 ms 2148 KB