Submission #337866
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <functional> #include <set> #define MX 300 #define MOD 1000000007 using namespace std; typedef long long int ll; ll dp[2][MX][MX]; char str[MX]; int main() { int n,m; scanf("%d %d",&n,&m); scanf("%s",&str); int pos=0; memset(dp[pos],0,sizeof(dp[pos])); dp[pos][0][0]=1; for(int i=0;i<n;i++) { pos^=1; memset(dp[pos],0,sizeof(dp[pos])); if(str[i]!='?') { if(str[i]!='2'&&str[i]!='5') { for(int j=0;j<=m;j++) { for(int k=0;k<=n;k++) { if(dp[pos^1][j][k]==0) continue; dp[pos][j][0]+=dp[pos^1][j][k]; if(dp[pos][j][0]>=MOD) dp[pos][j][0]-=MOD; } } } else if(str[i]=='2') { for(int j=0;j<=m;j++) { for(int k=0;k<=n;k++) { if(dp[pos^1][j][k]==0) continue; int nxt=k%2==0?k+1:1; dp[pos][j][nxt]+=dp[pos^1][j][k]; if(dp[pos][j][nxt]>=MOD) dp[pos][j][nxt]-=MOD; } } } else { for(int j=0;j<=m;j++) { for(int k=0;k<=n;k++) { if(dp[pos^1][j][k]==0) continue; int nxt=k%2==1?k+1:0; int nb=min(m,j+(nxt+1)/2); dp[pos][nb][nxt]+=dp[pos^1][j][k]; if(dp[pos][nb][nxt]>=MOD) dp[pos][nb][nxt]-=MOD; } } } } else { for(int j=0;j<=m;j++) { for(int k=0;k<=n;k++) { if(dp[pos^1][j][k]==0) continue; dp[pos][j][0]+=dp[pos^1][j][k]*8LL%MOD; if(dp[pos][j][0]>=MOD) dp[pos][j][0]-=MOD; int nxt=k%2==0?k+1:1; dp[pos][j][nxt]+=dp[pos^1][j][k]; if(dp[pos][j][nxt]>=MOD) dp[pos][j][nxt]-=MOD; nxt=k%2==1?k+1:0; int nb=min(m,j+(nxt+1)/2); dp[pos][nb][nxt]+=dp[pos^1][j][k]; if(dp[pos][nb][nxt]>=MOD) dp[pos][nb][nxt]-=MOD; } } } } int ret=0; for(int i=0;i<=n;i++) { ret+=dp[pos][m][i]; if(ret>=MOD) ret-=MOD; } printf("%d\n",ret); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - ニコニコ文字列2 |
User | yutaka1999 |
Language | C++ (G++ 4.6.4) |
Score | 20 |
Code Size | 2022 Byte |
Status | AC |
Exec Time | 100 ms |
Memory | 2212 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:22:17: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[300]’ [-Wformat] ./Main.cpp:21:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ./Main.cpp:22:18: 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 | 25 ms | 2088 KB |
sample_02.txt | AC | 27 ms | 2080 KB |
subtask1_01.txt | AC | 25 ms | 2084 KB |
subtask1_02.txt | AC | 25 ms | 2080 KB |
subtask1_03.txt | AC | 27 ms | 2008 KB |
subtask1_04.txt | AC | 26 ms | 2016 KB |
subtask1_05.txt | AC | 36 ms | 2204 KB |
subtask1_06.txt | AC | 36 ms | 2204 KB |
subtask1_07.txt | AC | 34 ms | 2200 KB |
subtask1_08.txt | AC | 31 ms | 2208 KB |
subtask1_09.txt | AC | 29 ms | 2204 KB |
subtask1_10.txt | AC | 27 ms | 2084 KB |
subtask1_11.txt | AC | 44 ms | 2028 KB |
subtask1_12.txt | AC | 60 ms | 2212 KB |
subtask1_13.txt | AC | 44 ms | 2208 KB |
subtask1_14.txt | AC | 61 ms | 2204 KB |
subtask1_15.txt | AC | 65 ms | 2020 KB |
subtask1_16.txt | AC | 61 ms | 2072 KB |
subtask1_17.txt | AC | 100 ms | 2020 KB |
subtask1_18.txt | AC | 60 ms | 2080 KB |
subtask1_19.txt | AC | 90 ms | 2204 KB |
subtask1_20.txt | AC | 64 ms | 2076 KB |
subtask1_21.txt | AC | 41 ms | 2080 KB |
subtask1_22.txt | AC | 42 ms | 2200 KB |