Submission #1794753
Source Code Expand
#include<bits/stdc++.h> using namespace std; using vi = vector< int >; using vii = vector< vi >; const int mod = 1e9 + 7; int main() { int N, X; string S; cin >> N >> X; cin >> S; vii dp(N + 2, vi(X + 1)); dp[0][0] = 1; for(int i = 0; i < N; i++) { vii dp2(N + 2, vi(X + 1)); for(int l = 0; l < 10; l++) { if(S[i] != '?' && S[i] - '0' != l) continue; for(int j = N; j >= 0; j--) { for(int k = X; k >= 0; k--) { if(l == 2) { if(j % 2 == 0) (dp2[j + 1][k] += dp[j][k]) %= mod; else(dp2[1][k] += dp[j][k]) %= mod; } else if(l == 5 && j % 2 == 1) { (dp2[j + 1][min(X, k + (j + 1) / 2)] += dp[j][k]) %= mod; } else { (dp2[0][k] += dp[j][k]) %= mod; } } } } dp.swap(dp2); } int ret = 0; for(int i = 0; i <= N; i++) { (ret += dp[i][X]) %= mod; } cout << ret << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - ニコニコ文字列2 |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 20 |
Code Size | 980 Byte |
Status | AC |
Exec Time | 407 ms |
Memory | 824 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 | sample_01.txt, sample_02.txt, 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 | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 256 KB |
subtask1_04.txt | AC | 1 ms | 256 KB |
subtask1_05.txt | AC | 5 ms | 256 KB |
subtask1_06.txt | AC | 17 ms | 384 KB |
subtask1_07.txt | AC | 7 ms | 256 KB |
subtask1_08.txt | AC | 24 ms | 384 KB |
subtask1_09.txt | AC | 8 ms | 256 KB |
subtask1_10.txt | AC | 3 ms | 256 KB |
subtask1_11.txt | AC | 13 ms | 256 KB |
subtask1_12.txt | AC | 182 ms | 824 KB |
subtask1_13.txt | AC | 14 ms | 256 KB |
subtask1_14.txt | AC | 172 ms | 820 KB |
subtask1_15.txt | AC | 140 ms | 820 KB |
subtask1_16.txt | AC | 143 ms | 820 KB |
subtask1_17.txt | AC | 407 ms | 820 KB |
subtask1_18.txt | AC | 57 ms | 820 KB |
subtask1_19.txt | AC | 396 ms | 820 KB |
subtask1_20.txt | AC | 154 ms | 820 KB |
subtask1_21.txt | AC | 8 ms | 256 KB |
subtask1_22.txt | AC | 5 ms | 256 KB |