Submission #337875
Source Code Expand
#include <stdio.h> #include <algorithm> #include <iostream> #include <vector> using namespace std; #define pb push_back #define mod 1000000007 typedef long long ll; int n,x,c; ll dp[255][255][255][2]; string s; int main() { cin >> n >> x; cin >> s; dp[0][0][0][0] = 1ll; for(int i=0;i<s.size();i++) { for(int j=0;j<=252;j++) { for(int k=0;k<=252;k++) { if(dp[i][j][k][0] == 0) goto nxt; c = (s[i]=='?')?10:1; if(s[i]=='?' || s[i]=='2') { dp[i+1][j][k][1] = (dp[i+1][j][k][1]+dp[i][j][k][0])%mod; c--; } dp[i+1][j][0][0] = (dp[i+1][j][0][0]+dp[i][j][k][0]*1ll*c)%mod; nxt:; if(dp[i][j][k][1] == 0) continue; c = (s[i]=='?')?10:1; if(s[i]=='?' || s[i]=='5') { dp[i+1][min(252,j+k+1)][k+1][0] = (dp[i+1][min(252,j+k+1)][k+1][0]+dp[i][j][k][1])%mod; c--; } if(s[i]=='?' || s[i]=='2') { dp[i+1][j][0][1] = (dp[i+1][j][0][1]+dp[i][j][k][1])%mod; c--; } dp[i+1][j][0][0] = (dp[i+1][j][0][0]+dp[i][j][k][1]*1ll*c)%mod; } } } ll res = 0; for(int i=x;i<=252;i++) for(int j=0;j<=252;j++) res = (res+dp[s.size()][i][j][0]+dp[s.size()][i][j][1])%mod; cout << res << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - ニコニコ文字列2 |
User | IH19980412 |
Language | C++ (G++ 4.6.4) |
Score | 20 |
Code Size | 1266 Byte |
Status | AC |
Exec Time | 812 ms |
Memory | 219040 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 | 30 ms | 800 KB |
sample_02.txt | AC | 43 ms | 1192 KB |
subtask1_01.txt | AC | 30 ms | 800 KB |
subtask1_02.txt | AC | 28 ms | 796 KB |
subtask1_03.txt | AC | 28 ms | 920 KB |
subtask1_04.txt | AC | 27 ms | 816 KB |
subtask1_05.txt | AC | 229 ms | 11296 KB |
subtask1_06.txt | AC | 205 ms | 18844 KB |
subtask1_07.txt | AC | 340 ms | 77992 KB |
subtask1_08.txt | AC | 158 ms | 29220 KB |
subtask1_09.txt | AC | 143 ms | 23708 KB |
subtask1_10.txt | AC | 79 ms | 7080 KB |
subtask1_11.txt | AC | 322 ms | 20772 KB |
subtask1_12.txt | AC | 324 ms | 22560 KB |
subtask1_13.txt | AC | 462 ms | 83812 KB |
subtask1_14.txt | AC | 410 ms | 67480 KB |
subtask1_15.txt | AC | 606 ms | 143520 KB |
subtask1_16.txt | AC | 587 ms | 133416 KB |
subtask1_17.txt | AC | 812 ms | 219040 KB |
subtask1_18.txt | AC | 273 ms | 1704 KB |
subtask1_19.txt | AC | 800 ms | 218908 KB |
subtask1_20.txt | AC | 579 ms | 131112 KB |
subtask1_21.txt | AC | 812 ms | 219040 KB |
subtask1_22.txt | AC | 468 ms | 82340 KB |