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
2015-02-14 17:17:47+0900
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
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