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 |
|
|
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 |