Submission #337876
Source Code Expand
#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif
#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64 int64_t
#define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v) ((i64)((v).size()))
#define bit(n) (((i64)1)<<((i64)(n)))
#define all(v) (v).begin(), (v).end()
std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top(); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }
#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...) \
{ \
DBG_LINE(); \
DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
DBG_OUT << std::endl; \
}
const i64 MAX = 256;
i64 dp[MAX][MAX][MAX];
const i64 MOD = 1e9 + 7;
string s;
i64 recur(i64 pos, i64 track, i64 rem)
{
rem = max(rem, (i64)0);
if(pos == sz(s)) return rem == 0 ? 1 : 0;
i64 &res = dp[pos][track][rem];
if(res != -1) return res;
res = 0;
for(i64 c = 0; c <= 9; ++c){
if(s[pos] != '?' && s[pos] != '0' + c) continue;
i64 next_track = 0;
i64 next_rem = rem;
if(c == 2) next_track = 1;
if(c == 2 && track % 2 == 0) next_track = track + 1;
if(c == 5 && track % 2 == 1) next_track = track + 1, next_rem = rem - (track + 1) / 2;
res = (res + recur(pos + 1, next_track, next_rem)) % MOD;
}
//DEBUG(pos, track, rem, res);
return res;
}
int main()
{
i64 n, k;
cin >> n >> k >> s;
memset(dp, -1, sizeof(dp));
cout << recur(0, 0, k) << endl;
}
Submission Info
Submission Time |
|
Task |
A - ニコニコ文字列2 |
User |
Komaki |
Language |
C++11 (GCC 4.8.1) |
Score |
20 |
Code Size |
4803 Byte |
Status |
AC |
Exec Time |
544 ms |
Memory |
131880 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 |
272 ms |
131872 KB |
sample_02.txt |
AC |
266 ms |
131876 KB |
subtask1_01.txt |
AC |
293 ms |
131820 KB |
subtask1_02.txt |
AC |
265 ms |
131872 KB |
subtask1_03.txt |
AC |
265 ms |
131872 KB |
subtask1_04.txt |
AC |
266 ms |
131868 KB |
subtask1_05.txt |
AC |
267 ms |
131872 KB |
subtask1_06.txt |
AC |
267 ms |
131864 KB |
subtask1_07.txt |
AC |
270 ms |
131876 KB |
subtask1_08.txt |
AC |
287 ms |
131864 KB |
subtask1_09.txt |
AC |
276 ms |
131872 KB |
subtask1_10.txt |
AC |
272 ms |
131868 KB |
subtask1_11.txt |
AC |
273 ms |
131868 KB |
subtask1_12.txt |
AC |
269 ms |
131864 KB |
subtask1_13.txt |
AC |
264 ms |
131868 KB |
subtask1_14.txt |
AC |
274 ms |
131872 KB |
subtask1_15.txt |
AC |
286 ms |
131876 KB |
subtask1_16.txt |
AC |
286 ms |
131880 KB |
subtask1_17.txt |
AC |
544 ms |
131880 KB |
subtask1_18.txt |
AC |
266 ms |
131872 KB |
subtask1_19.txt |
AC |
463 ms |
131872 KB |
subtask1_20.txt |
AC |
291 ms |
131872 KB |
subtask1_21.txt |
AC |
277 ms |
131868 KB |
subtask1_22.txt |
AC |
267 ms |
131868 KB |