Submission #359176
Source Code Expand
//ドワンゴ フィッシング 8020
//写経させて頂きました
//http://dwango2015-honsen.contest.atcoder.jp/submissions/337867
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,pair<int,int>> PP;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1e9;
const int MOD = 1e9+7;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int N,X;
string s;
ll dp[303][303][303][2];
//x文字目
//n個にこにー文字列がある
//m個にこにー文字列が連続
//a 0:'5'だった(又はにこにー文字列が終わってる) 1:'2'だった
int dfs(int x,int n,int m,int a){
n = min(255,n);
m = min(255,m);
if(dp[x][n][m][a] != -1)return dp[x][n][m][a];
if(x == s.size())return n >= X;
vector<int> p;
if(s[x] == '?')for(int i=0;i<10;i++)p.push_back(i);
else p.push_back(s[x] - '0');
int ans = 0;
for(int i=0;i<p.size();i++){
int t = p[i];
if(a == 0 && t == 2){
ans += dfs(x+1,n,m,1);
}else if(a == 1 && t == 5){
ans += dfs(x+1,n+m+1,m+1,0);
}else if(t == 2){
ans += dfs(x+1,n,0,1);
}else{
ans += dfs(x+1,n,0,0);
}
ans %= MOD;
}
return dp[x][n][m][a] = ans % MOD;
}
int main(void) {
memset(dp,-1,sizeof(dp));
cin >> N >> X >> s;
cout << dfs(0,0,0,0) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - ニコニコ文字列2 |
User |
tkzw_21 |
Language |
C++11 (GCC 4.8.1) |
Score |
0 |
Code Size |
1344 Byte |
Status |
MLE |
Exec Time |
1775 ms |
Memory |
436024 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
MLE |
815 ms |
435832 KB |
sample_02.txt |
MLE |
793 ms |
435828 KB |
subtask1_01.txt |
MLE |
787 ms |
435828 KB |
subtask1_02.txt |
MLE |
778 ms |
435828 KB |
subtask1_03.txt |
MLE |
797 ms |
435824 KB |
subtask1_04.txt |
MLE |
785 ms |
435824 KB |
subtask1_05.txt |
MLE |
792 ms |
436024 KB |
subtask1_06.txt |
MLE |
782 ms |
435832 KB |
subtask1_07.txt |
MLE |
815 ms |
435828 KB |
subtask1_08.txt |
MLE |
852 ms |
435788 KB |
subtask1_09.txt |
MLE |
798 ms |
435828 KB |
subtask1_10.txt |
MLE |
796 ms |
435824 KB |
subtask1_11.txt |
MLE |
771 ms |
435956 KB |
subtask1_12.txt |
MLE |
789 ms |
435956 KB |
subtask1_13.txt |
MLE |
783 ms |
435956 KB |
subtask1_14.txt |
MLE |
795 ms |
435952 KB |
subtask1_15.txt |
MLE |
839 ms |
435952 KB |
subtask1_16.txt |
MLE |
841 ms |
435956 KB |
subtask1_17.txt |
MLE |
1775 ms |
435960 KB |
subtask1_18.txt |
MLE |
783 ms |
435920 KB |
subtask1_19.txt |
MLE |
1469 ms |
435956 KB |
subtask1_20.txt |
MLE |
831 ms |
435824 KB |
subtask1_21.txt |
MLE |
1743 ms |
435896 KB |
subtask1_22.txt |
MLE |
801 ms |
435960 KB |