Submission #337882


Source Code Expand

#include <cstdio>
const int mod = 1000000007;
int dp[260][260][260];
inline int min(int x, int y) { return x < y ? x : y; }
void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}
int main() {
	int n, x;
	char s[260];
	scanf("%d%d", &n, &x);
	scanf("%s", s);
	dp[0][0][0] = 1;
	for (int i = 0; s[i]; i++) {
		for (int j = 0; j <= x; j++) {
			for (int k = 0; k <= i; k++) {
				if (!dp[i][j][k]) continue;
				if (s[i] == '2') {
					if (k & 1) {
						add(dp[i+1][j][1], dp[i][j][k]);
					} else {
						add(dp[i+1][j][k+1], dp[i][j][k]);
					}
				} else if (s[i] == '5') {
					if (k & 1) {
						add(dp[i+1][min(j+k/2+1,x)][k+1], dp[i][j][k]);
					} else {
						add(dp[i+1][j][0], dp[i][j][k]);
					}
				} else if (s[i] != '?') {
					add(dp[i+1][j][0], dp[i][j][k]);
				} else {
					if (k & 1) {
						add(dp[i+1][j][1], dp[i][j][k]);
					} else {
						add(dp[i+1][j][k+1], dp[i][j][k]);
					}
					if (k & 1) {
						add(dp[i+1][min(j+k/2+1,x)][k+1], dp[i][j][k]);
					} else {
						add(dp[i+1][j][0], dp[i][j][k]);
					}
					add(dp[i+1][j][0], (int)((long long)dp[i][j][k] * 8 % mod));
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		add(ans, dp[n][x][i]);
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time
Task A - ニコニコ文字列2
User nwin
Language C++ (G++ 4.6.4)
Score 20
Code Size 1296 Byte
Status AC
Exec Time 220 ms
Memory 57880 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:12:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:13:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 22 ms 804 KB
sample_02.txt AC 21 ms 928 KB
subtask1_01.txt AC 22 ms 792 KB
subtask1_02.txt AC 21 ms 800 KB
subtask1_03.txt AC 21 ms 672 KB
subtask1_04.txt AC 21 ms 696 KB
subtask1_05.txt AC 25 ms 1952 KB
subtask1_06.txt AC 40 ms 5656 KB
subtask1_07.txt AC 28 ms 1692 KB
subtask1_08.txt AC 50 ms 8416 KB
subtask1_09.txt AC 32 ms 4004 KB
subtask1_10.txt AC 25 ms 2164 KB
subtask1_11.txt AC 31 ms 3628 KB
subtask1_12.txt AC 91 ms 6948 KB
subtask1_13.txt AC 27 ms 2460 KB
subtask1_14.txt AC 109 ms 18340 KB
subtask1_15.txt AC 153 ms 38820 KB
subtask1_16.txt AC 146 ms 36648 KB
subtask1_17.txt AC 220 ms 57880 KB
subtask1_18.txt AC 78 ms 1640 KB
subtask1_19.txt AC 206 ms 57768 KB
subtask1_20.txt AC 146 ms 36260 KB
subtask1_21.txt AC 26 ms 1836 KB
subtask1_22.txt AC 25 ms 1956 KB