Submission #359177
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;
int 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 |
20 |
Code Size |
1345 Byte |
Status |
AC |
Exec Time |
1472 ms |
Memory |
218228 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 |
476 ms |
218088 KB |
sample_02.txt |
AC |
477 ms |
218088 KB |
subtask1_01.txt |
AC |
483 ms |
218092 KB |
subtask1_02.txt |
AC |
477 ms |
218092 KB |
subtask1_03.txt |
AC |
476 ms |
218096 KB |
subtask1_04.txt |
AC |
480 ms |
218088 KB |
subtask1_05.txt |
AC |
477 ms |
218216 KB |
subtask1_06.txt |
AC |
482 ms |
218220 KB |
subtask1_07.txt |
AC |
514 ms |
218220 KB |
subtask1_08.txt |
AC |
550 ms |
218092 KB |
subtask1_09.txt |
AC |
504 ms |
218212 KB |
subtask1_10.txt |
AC |
481 ms |
218096 KB |
subtask1_11.txt |
AC |
478 ms |
218220 KB |
subtask1_12.txt |
AC |
486 ms |
218220 KB |
subtask1_13.txt |
AC |
502 ms |
218228 KB |
subtask1_14.txt |
AC |
493 ms |
218204 KB |
subtask1_15.txt |
AC |
533 ms |
218224 KB |
subtask1_16.txt |
AC |
528 ms |
218220 KB |
subtask1_17.txt |
AC |
1472 ms |
218224 KB |
subtask1_18.txt |
AC |
478 ms |
218220 KB |
subtask1_19.txt |
AC |
1185 ms |
218220 KB |
subtask1_20.txt |
AC |
537 ms |
218216 KB |
subtask1_21.txt |
AC |
1461 ms |
218216 KB |
subtask1_22.txt |
AC |
503 ms |
218216 KB |