QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73720 | #3528. Cockroach Racing | sinbad | AC ✓ | 245ms | 18924kb | C++ | 7.9kb | 2023-01-27 19:09:12 | 2023-01-27 19:09:13 |
Judging History
answer
// #define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
constexpr inline int lg2(int64 x) { return x == 0 ? -1 : sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
constexpr inline int p2ceil(int64 x) { return 1 << (lg2(x - 1) + 1); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
inline void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
inline void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
inline int mod(int x) { return x >= MOD ? x - MOD : x; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
template <int MOD_> struct modnum {
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
private:
int v;
static int minv(int a, int m) {
a %= m; assert(a);
return a == 1 ? 1 : int(m - int64(minv(m, a)) * int64(m) / a);
}
public:
modnum() : v(0) {}
modnum(int64 v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
explicit operator int() const { return v; }
friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
friend std::istream& operator >> (std::istream& in, modnum& n) { int64 v_; in >> v_; n = modnum(v_); return in; }
friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
modnum inv() const { modnum res; res.v = minv(v, MOD); return res; }
friend modnum inv(const modnum& m) { return m.inv(); }
modnum neg() const { modnum res; res.v = v ? MOD-v : 0; return res; }
friend modnum neg(const modnum& m) { return m.neg(); }
modnum operator- () const { return neg(); }
modnum operator+ () const { return modnum(*this); }
modnum& operator ++ () { ++v; if (v == MOD) v = 0; return *this; }
modnum& operator -- () { if (v == 0) v = MOD; --v; return *this; }
modnum& operator += (const modnum& o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
modnum& operator -= (const modnum& o) { v -= o.v; if (v < 0) v += MOD; return *this; }
modnum& operator *= (const modnum& o) { v = int(int64(v) * int64(o.v) % MOD); return *this; }
modnum& operator /= (const modnum& o) { return *this *= o.inv(); }
friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
friend modnum power(modnum a, int64 n) {
modnum ret = 1;
for (; n; n >>= 1) {
if (n & 1) ret *= a;
a *= a;
}
return ret;
}
};
using mint = modnum<MOD>;
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
reverse(s[i].begin(), s[i].end());
}
trace(s);
auto col = vect<int>(0, m, n + 1, 10);
for (int pos = 0; pos < m; ++pos) {
for (int i = 0; i < n; ++i) {
col[pos][i + 1] = col[pos][i];
if (s[i][pos] == '?') {
for (int k = 0; k < 10; ++k) col[pos][i + 1][k]++;
} else {
int x = s[i][pos] - '0';
col[pos][i + 1][x]++;
}
}
}
vector<mint> p10(m + 1);
for (int i = 0; i <= m; ++i) p10[i] = i == 0 ? 1 : p10[i - 1] * 10;
auto dp = vect<array<mint, 2>>({0, 0}, n + 1, n, m, 11); // [sum, cnt]
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
for (int pos = 0; pos < m; ++pos) {
for (int x = 9; x >= 0; --x) {
for (int len = 0; len <= j - i + 1; ++len) {
if (col[pos][i + len][x] - col[pos][i][x] != len) continue;
trace("!!!!", i, j, pos, x, len);
auto t1 = len == 0
? array<mint, 2>{0, 1}
: (pos > 0 ? dp[i][i + len - 1][pos - 1][0]
: (len > 1 ? array<mint, 2>{0, 0} : array<mint, 2>{0, 1}));
auto t2 = len == j - i + 1
? array<mint, 2>{0, 1}
: (i + len < n ? dp[i + len][j][pos][x + 1] : array<mint, 2>{0, 1});
trace(i, j, pos, x, len, t1, t2);
mint sum = (x * p10[pos] * len * t1[1] + t1[0]) * t2[1] + t2[0] * t1[1];
mint cnt = t2[1] * t1[1];
trace(sum, cnt);
dp[i][j][pos][x][0] += sum;
dp[i][j][pos][x][1] += cnt;
trace(i, j, pos, x, len, "done", dp[i][j][pos][x]);
}
}
}
}
}
cout << dp[0][n - 1][m - 1][0][0] << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3388kb
input:
2 2 ?? ??
output:
490050
result:
ok 1 number(s): "490050"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3328kb
input:
2 3 4?? ??2
output:
6403775
result:
ok 1 number(s): "6403775"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3368kb
input:
4 1 0 ? 4 8
output:
42
result:
ok 1 number(s): "42"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
9 9 ??08???90 ??767??7? ?7????297 6?7?06257 ?002?3??? 8?4250??? 9????0270 933??10?? 977?4747?
output:
780526017
result:
ok 1 number(s): "780526017"
Test #5:
score: 0
Accepted
time: 0ms
memory: 4348kb
input:
19 19 ??3?7??007?845??2?? 0?7?4?8143?20?2??5? ??7???1??30???53?2? ?????9?2616629????6 1????33?641???????? ??6605?16????492?42 307??0?7343?836??2? ?41169?140???05??3? 3??94????0?33??769? ?9219??5??3??9?18?0 5??82010??48?9??02? 6?087?05???07?0?722 ?0?34?86?29?96?4?9? 6???22?2????1??20?5 67??2?9?8?????...
output:
658914611
result:
ok 1 number(s): "658914611"
Test #6:
score: 0
Accepted
time: 46ms
memory: 17964kb
input:
49 49 0?5?3?6?5????1??7?9???9??1???7883808?5?8??5???63? ?49????4?50??844?30?4??5???04?08???2?03?1?2?????? ?????42??0?444?01???2?41?5?2???161528?36??85????? ?7?7?????65??????5?9?2??8??6????4?81441?0??555?0? ?25?16?????2???70?259???5????3?5?1219???09?953??4 125?53880???6893??97705996??20????08?????3??...
output:
794517533
result:
ok 1 number(s): "794517533"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
10 10 0????????? ?????????? ??????2??5 ?????????? 3????5?4?? ??6??????? ????2????? ???62????? ??6??????1 ???????9??
output:
373003917
result:
ok 1 number(s): "373003917"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
10 10 ???????720 ??3??2???? ??05????66 ?6???????? 49???????? 6?0?4?9??? ??8???87?? ???2?????? 77???????? ?????6????
output:
295277581
result:
ok 1 number(s): "295277581"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
10 10 ???32??11? ????2??8?? 12??7???8? 2???0??7?? ?????0??8? 3??0?0?65? ???6?4?866 5605??3?81 6?6?35???? ??2?????1?
output:
771798451
result:
ok 1 number(s): "771798451"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
10 10 0?6143?68? 2404??6847 36?792108? 4??02??708 411842??8? ?6?5062064 54613?7?96 752585840? 7693?6??89 ??0982??83
output:
894510331
result:
ok 1 number(s): "894510331"
Test #11:
score: 0
Accepted
time: 3ms
memory: 3520kb
input:
10 10 035411442? ?41?317918 2528?53977 393?321??1 456515667? 515?229158 ?6?7637035 59??270?57 794??36593 9?85474573
output:
438146771
result:
ok 1 number(s): "438146771"
Test #12:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
10 20 1????03????????????? ?0???2?????2???????? ???49??????4???????? ???6???????2??8?6??? 5??????????????????8 ??????3????2???????? ???????????????7???? ??????5??9?????????? ??1???????????1?3??4 ??????3??????3?677??
output:
84063386
result:
ok 1 number(s): "84063386"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
10 20 0??????5???70???2??6 0????9??6??????????? ?0???9?4???8???1?15? 38???9?????9??2?8??? ????81??0?9?1??1???? ?????9??????????0??? ?????1??982??32????4 7???3?4??????8????3? ?7??0?????????9????? ??9????9?7?9????????
output:
560480313
result:
ok 1 number(s): "560480313"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
10 20 11??476366?5?????038 1???0?9???1?1?4??7?? ?98??3?5?4?295571??? 3?155?8?????163?2??? ??9484???97?254???6? ?462?5???481??0???31 4??11?0?2???6???9??? 52?3???198???????2?? ?5?5??928?????3??2?? ?4?2??1364????81800?
output:
677516333
result:
ok 1 number(s): "677516333"
Test #15:
score: 0
Accepted
time: 4ms
memory: 3688kb
input:
10 20 108???8594118?88??72 1?4??0?49919?4??8553 ?37626306?4??05?5?73 6840383??502?5?63??7 ?957911?911699?1?858 ?990016971165787?582 721202756140622?49?0 80?0??48????2?501451 9683105?22?615479?0? 96?62099900?3??76300
output:
748614195
result:
ok 1 number(s): "748614195"
Test #16:
score: 0
Accepted
time: 3ms
memory: 3676kb
input:
10 20 0153571811059179671? 108455749027?3920418 ?1?43032879107395723 34650?889837215122?4 43?6587865?8?1063850 8117?154031662462430 8418294265?25??33102 898756?4670623028928 905599266?16?0855?31 ?66832962163?503242?
output:
943616887
result:
ok 1 number(s): "943616887"
Test #17:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
10 50 ??????5?6??40??????????????9????2????????????????? ??????0???????7????8??????????????7??????2??????3? ????6????0???????????????????????3???????????????? ????2????5?????1??5?????????4?05?????????5?9?????? ??????9?????5?????????????????????9????????1?3???? ??????????????????????8????????????????...
output:
302976629
result:
ok 1 number(s): "302976629"
Test #18:
score: 0
Accepted
time: 4ms
memory: 4104kb
input:
10 50 ?4??0???????9?2?2???????0???3??????7?4??2??75???4? ???????7?6???8?4????7????0???????8?9?86?????1??8?2 ?????0?69??3?90?597???1?12???6?62?8??????????27??? ????????3???????380?9??????3?????8??7?????0????71? ?5??7?3??3??????????9?3??????00?3?9???4??????8??69 ???1?2??????91???4???8???5????4???4??9?...
output:
301976692
result:
ok 1 number(s): "301976692"
Test #19:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
10 50 0??????2??2???51??6?12484801??6??7????????1944???4 ?38?5?5?6??????71832???1?????40??7??9???5?7?82??81 1??4?05?0?8?174??76??5?956?135???40?4?428?1?2??23? 4??4??774?83?7?255??4??88?09766603??38?6??739?6015 630?7??4?0????32?5??0????778?3???????????0???6379? 739709617?999?773?3418301?79?76?587?309...
output:
509626305
result:
ok 1 number(s): "509626305"
Test #20:
score: 0
Accepted
time: 4ms
memory: 4204kb
input:
10 50 0487??10817??1?16?71?54184557?9876900672102?895??3 4?81?3?028?98?42?26206?754?617?59?657???7212769891 5927?48????40404887634???6?51?47460?5?2???835?3?47 6?38894316?6738?644??21????966259183263?309?76?47? 64?52113283940?7?58064?6313573013?7?6151?9592???27 8349444???6759347?7523?6?8???5777?6391?...
output:
827241925
result:
ok 1 number(s): "827241925"
Test #21:
score: 0
Accepted
time: 3ms
memory: 4080kb
input:
10 50 ?4?79633?643976?63250753375396461365544512?78?35?4 14??221689365403375417594?231044?762893??3?267?979 ?51?491386057?509?906?1?28428275985810035?14?19845 2?040?163678410917662928842186149125811??218971906 355353125?6209649??6796449?2878?266152774911284760 3714438373?718562?4510708?9168593444832...
output:
664103560
result:
ok 1 number(s): "664103560"
Test #22:
score: 0
Accepted
time: 4ms
memory: 4000kb
input:
20 10 ?????????? ????????57 ?????4??6? ??2??8??8? ?????????? ????6????? ???8?????? ?????????? 4????7??9? ???1???1?? 4????????? ?????????? ?????????? ?3???????? ??1??????3 ??????6?2? ?????????? ?????????? ?5???????? ??????5??4
output:
384126155
result:
ok 1 number(s): "384126155"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3908kb
input:
20 10 ??????2??? ??1????2?? ?1??2?0??? ?????????? ????????8? ?98092??2? ??453????? ????????0? 3????649?? ?9?2?15?5? 4??1?????2 ?3???35??7 ?????????? ?????22?1? ???3?7??2? ??????4??6 ?????5???1 7???????3? ??3?9??8?? 8??1????8?
output:
97199393
result:
ok 1 number(s): "97199393"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
20 10 002?3??012 ?1460?424? ???7??48?4 ?4?3521?97 ??650611?3 ?3??1?9??? ?????6??80 16?0?0?5?? 17???????? ?8?9?79??? 3??4??53?? ?8?265?6?5 5022812?34 ?5?6?????? ?7?335?1?? 59?8?87?5? 6??4?0?4?8 78????16?? ???63????9 ??28?01895
output:
970610157
result:
ok 1 number(s): "970610157"
Test #25:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
20 10 ??6427?355 0?4736502? 139022861? ??44605?51 2321570082 2501432??8 29202789?1 311???420? 3247?8042? ?881??98?6 4274?962?? 44116?159? 4?637804?2 ???4451761 ?68?484277 6356514??6 6554356736 817?511935 ??48725824 9967?2?757
output:
777766220
result:
ok 1 number(s): "777766220"
Test #26:
score: 0
Accepted
time: 4ms
memory: 3916kb
input:
20 10 ?5?0443?45 2552451909 3?95468846 358?4230?6 37?4?2?106 38?5278788 41742?4379 45?6?80664 4?6?21?316 520358?02? ?742675127 58?45365?3 65?9934??7 6798553448 77?89?7969 7884864904 8188?6??75 87?2456758 8840?40183 9245265930
output:
848368858
result:
ok 1 number(s): "848368858"
Test #27:
score: 0
Accepted
time: 12ms
memory: 4508kb
input:
20 20 ????????????????1??? ??????????????????96 ??????6?????8??????? 2?????????????????7? ?????3???????1?????? ??6??7????????????2? ??????5???4????????0 ?????9?????????????? ?????????????6?????? ???????????????6???? ???????7?3??????3??? ????????6????????4?? 5???2??9???1?8???0?? ???2?????2??8??????? ...
output:
67854164
result:
ok 1 number(s): "67854164"
Test #28:
score: 0
Accepted
time: 4ms
memory: 4536kb
input:
20 20 ???????????????8?5?? ???????6?6?0?0???72? ????????????2??2??2? ?????4?0???????????? ??1????3??4????64??? 3?0??5?5?7?????307?? ?????????1???83???69 ???????29?9???8????? ?1????0??6?35?3?7??? ????0??????????????? ?????0?????783?????6 ?0?18?17???????5???? ??????5??????4??7??? ????0??????767???5?? ...
output:
956277142
result:
ok 1 number(s): "956277142"
Test #29:
score: 0
Accepted
time: 4ms
memory: 4432kb
input:
20 20 09?1?0???154???58?8? ??5?7599?87?22??8956 ?95?7???7?188?903??? 2?0????99588??346116 347?7???????142???65 ????6??9?4?941?33??? 3???89?94?6?1??88??8 ??3?76???9??5?6??5?4 46??32???8??97?1???5 ???801?28????9?96??? ???8?870??4?970?54?? 5?6??????0???222779? ?7?021?8?4????2????7 6???69????027388?3?3 ...
output:
976947581
result:
ok 1 number(s): "976947581"
Test #30:
score: 0
Accepted
time: 3ms
memory: 4540kb
input:
20 20 083095228?5?2644?168 10392020300554638700 30??386?6717?881758? 3239??882040095554?0 38?40?5219?053884469 394?5?0075?02?41?6?? ???1742?64?41102???4 5008?728?5?6??53?311 53436403?0?33?198645 54717324?98921941?59 ??3?360?12?285?7?8?? ?39828?6?6?5?9210??4 6?350?5?1?5322049?27 ?58739015?476376162? ...
output:
51567474
result:
ok 1 number(s): "51567474"
Test #31:
score: 0
Accepted
time: 7ms
memory: 4444kb
input:
20 20 0?23153440476153105? 09061873814519257143 ?202?799560072466388 1218?651?5?204452589 207?1937293118?02140 ?32?1987721668387?3? 2432922?6761?9?04138 2579?12??6?29???1?91 28?75812799484303849 43593?79148?31?903?5 46224442256853014570 52061320?93414541493 5304238?085837549931 67776952060?1?1?8?87 ...
output:
225558553
result:
ok 1 number(s): "225558553"
Test #32:
score: 0
Accepted
time: 11ms
memory: 6044kb
input:
20 50 ?2??????6????????????????????????????????0??0????? ??????????????????????2??????7???????????7???????? 2????????0?????????????3??5????????????????????3?? ????????5???30????????????3???4??????47???????8??? ??3???1?????????????????????????2??5????????4????8 ??????????1?25??????????????9????7?????...
output:
678184250
result:
ok 1 number(s): "678184250"
Test #33:
score: 0
Accepted
time: 11ms
memory: 6008kb
input:
20 50 ???1???????0???17??????6?????2??8?4?48?2?????????? ?8??5??9?1??6????44????1??1?7?????????9?1??????23? 20????842???79?????6???80????02???0?39????????9??? 2?4??6???????6?????????535???????2??02?7????9??50? ??????????61?????7?????????0??7?????0???3?1?8??2?? 3413???????3?9??????????????????28??725...
output:
57297550
result:
ok 1 number(s): "57297550"
Test #34:
score: 0
Accepted
time: 3ms
memory: 6048kb
input:
20 50 03??8338?45?677??5??1???68?4??49?9?0?15?07?0?9?873 ?6?7????????83?4????????91?895??79?9????1?7??7?5?1 1?357??659??5??5?6???84???8??68??1160?????21?8??47 ?27?45???????41?54?572?4??1??8?9?0?3??61??5?5886?? 2???7?1????2???4????9??2?849277??7?934?29992180??? ??68911???76?935?566?59???5??0??914??25...
output:
584219333
result:
ok 1 number(s): "584219333"
Test #35:
score: 0
Accepted
time: 8ms
memory: 6128kb
input:
20 50 1?525?6?497823?475?69?6492?157?4609889?980?5162?94 1728547?16279?3?0834209927?548?24686?4?88?753?2?84 281?6?92?9337975?10900??1691?920?757969?914?1?6095 30?84794??115?22908?22??7?41??3?79728?85?0122?8636 364280154?15??343542??9711??1?915?55354?570897?201 4078036??8?5?7593749?77?84?905?72??880?...
output:
121549800
result:
ok 1 number(s): "121549800"
Test #36:
score: 0
Accepted
time: 8ms
memory: 6124kb
input:
20 50 00?18359996770??863998??7056819?0223598059918?0853 02146371385183?368?4040?9167??123?86707770?1?676?7 03373293725341?9940886?7599?2030?614234022805602?? 056374196442793542?34?6143737952171?819990?159633? 12363981023395399915345863799?0599?085136168?08?63 125709533724163350923408644?10?07446?3?...
output:
754423372
result:
ok 1 number(s): "754423372"
Test #37:
score: 0
Accepted
time: 23ms
memory: 6616kb
input:
50 10 ??????0??? ?????????2 ???0?????? ?????????? ?????????8 ???2?????? ?????????? ?????????3 ???1?2???? ????4????8 ???4????6? ?3???????8 ?????????? ????94???5 ???3?????? ?7??????8? ?????????? ?????5???? ???????3?? ???2??6??? ?4??8??8?? ?????????? ??????3??? ????1????? ?????????? ?8???????? ????????...
output:
720198811
result:
ok 1 number(s): "720198811"
Test #38:
score: 0
Accepted
time: 13ms
memory: 6552kb
input:
50 10 0?320????? ?71??151?? ???0????2? ?2??9????? ??????0??? ?6???????? 2??5956??1 ?8?56???7? ??4?0?4?7? ?9??29???? ??8??6???? ?1????0??? ??296?387? ??561?30?? ??????0??? 3????98??3 ??????81?? ?????????? ?69???85?? ????77??5? ???68????? ?2???9???? ?4??44???? ?5??2????? ?????9???2 ???????4?7 5???????...
output:
880397834
result:
ok 1 number(s): "880397834"
Test #39:
score: 0
Accepted
time: 8ms
memory: 6560kb
input:
50 10 ??3996???? ????2?1?9? 042??851?0 ??58?688?2 04???215?5 ?7?20879?5 16?33??438 2?0??6???? ?11578?755 ??59?77?44 24??663??2 2?71???5?? 2?8??1??7? 29??767??3 ?19??????? ?19?9?8??? 3?682?395? 3?4??592?3 37????9??? ????14?88? ?6?1??03?? ????978??? ??9?4????? 53??4??289 ??1?96?4?? 5???42??9? 6008?177...
output:
436473853
result:
ok 1 number(s): "436473853"
Test #40:
score: 0
Accepted
time: 3ms
memory: 6640kb
input:
50 10 0238?52?43 0277?63089 0?9381?311 ?4?899??0? 063725413? ???904?6?? 08?60?9?20 0882?11?7? 09?1?03401 ?97?787?29 099?989?0? 10930402?8 11705?6?1? ?4?80?05?1 164?73?586 1???926?46 17?2724258 ?596?993?2 ?6921?8328 329?609?43 3666?1756? 373?3?676? 3?7886???1 ?173?8275? ??080?6?81 49768?44?? 53?25?56...
output:
486819799
result:
ok 1 number(s): "486819799"
Test #41:
score: 0
Accepted
time: 6ms
memory: 6584kb
input:
50 10 0436184989 04??41890? 05465614?8 072?3?13?? ?779743961 11641609?8 1?43353075 1260855865 1589?42??7 230887?68? 311234?81? 3?52655974 33?7235667 3435350313 3515413172 ?559?96?11 3766489294 4?82991774 44313332?6 ?62?353230 4646431908 48?15214?4 49834?0572 5066990844 5287357?57 ??81350?96 60679816...
output:
277980085
result:
ok 1 number(s): "277980085"
Test #42:
score: 0
Accepted
time: 38ms
memory: 9676kb
input:
50 20 ?18??7????????????06 ???0?????????9?????? ??????4??0?????????? ?????????9?38??????? ??????4?????????9??? ??668???????7??0?6?? ??????2???0????????? ???????????????????? ??????62?1?????????? ???????93??7???????? 3??????8???????0???? 3??????????????9???? ???3??????4??8?????? ?????68????4?7?????? ...
output:
502169464
result:
ok 1 number(s): "502169464"
Test #43:
score: 0
Accepted
time: 27ms
memory: 9640kb
input:
50 20 ???8?4?2???4????98?? 0??4?6??7??3?2??5??? 0???72?33?3???8????8 0?4?8?????4?1???05?? ????7??8?0??5??????? ?826??????8?9?????0? ?05?3?011?1????1???? ?8????43?????3????7? 1?309?????4?????47?1 ??6????5?3?????94?3? 2??????????38??64?2? ?????????79????????? ?7?04????6?1???0???? ?????????????82???8? ...
output:
583076940
result:
ok 1 number(s): "583076940"
Test #44:
score: 0
Accepted
time: 17ms
memory: 9728kb
input:
50 20 ?0903?579993????3655 ?30?41???4?????7?5?4 ?3?10838????1???071? ?????046?007??085012 06?09?7???9684?8545? ??4?30341892?03?38?? ?79???81???9?2?5?496 ?94?0?31????????4?2? ?407????06483??09??? ???19??7?4?2??7?4?9? ???????81????99?9?02 19???05??31??46?424? ??94??9??647????09?? 2?????7?6?1??2?6???0 ...
output:
280419440
result:
ok 1 number(s): "280419440"
Test #45:
score: 0
Accepted
time: 14ms
memory: 9644kb
input:
50 20 00914????414???2?7?7 082?62719?3679??6617 0?4?2?7371?7868?8184 ?135018?0?5????25?1? 1435146?214??1?81?2? ?524?03?031?307??657 ?613?54?47??81?49338 19?1529614?98?070?7? ??084?424872?15047?9 235?616813?44?360382 246645143013697?1??5 2??2???32834789456?6 2639034390234???32?1 2780372859?358?42?03 ...
output:
813127409
result:
ok 1 number(s): "813127409"
Test #46:
score: 0
Accepted
time: 14ms
memory: 9696kb
input:
50 20 000502?94?4449??9994 0?3797520?15?593?793 02265363070904148599 ?3982451?84158192624 0922?01594870?0?4?34 ?949735434811923303? 0?90?419323550558?79 ??2?10?942176222006? 1?23252543?190089770 17812403623?93515579 ?87136951201?5278034 206?2357?60779829997 23108903723692?6462? 24?49387096110?360?1 ...
output:
702382634
result:
ok 1 number(s): "702382634"
Test #47:
score: 0
Accepted
time: 99ms
memory: 18924kb
input:
50 50 ?????????????????????67?3???1????????????????2??3? ?64?????4???????????????86??8?????1??????????????? 0???????????????8??????1???1?3???????1????0??????? ?97?22??????????????????????????6??9??????30?2???? ?????????????807??????6??????1?3?????????????????? ???7???????????02??????4??????9??1?????...
output:
34908478
result:
ok 1 number(s): "34908478"
Test #48:
score: 0
Accepted
time: 74ms
memory: 18884kb
input:
50 50 ??2????0??????1???????????6??4?432??2??9?????????? ?4??2?????04???4????2?7???????????2?18????7?????0? ?4?7?0?58??64???????7???62???8????2???9?????????1? ?5???9????7???????????????????????3?21???????????? ???7????????1?73???????????3??????0???32?????782?? ??1???01????05?38????6?9????54?????????...
output:
400228884
result:
ok 1 number(s): "400228884"
Test #49:
score: 0
Accepted
time: 48ms
memory: 18840kb
input:
50 50 0???97964?5?8??943???7?7??81?8???27?14?9?5?69????? 04???6?5?66306??31??????248??801?5???31?33?9??4?0? ??77?99???1??88?7557?1?4?8?28?81???6777??92??9??1? ?7??39???5?????181411044???7?23366?6?4?0??99?9???? 0?7??86198???55??7?17?96????????960??4596????31??8 1??928317????00?55?1?091?6?03?5??????1?...
output:
46072945
result:
ok 1 number(s): "46072945"
Test #50:
score: 0
Accepted
time: 36ms
memory: 18896kb
input:
50 50 0712930?998?62?141?7??5944722063?0?1????03401?2709 ?9?874217604698?9?5477?081?79132?61?0200196?014600 1145926388498?1793?837047202?042??62??0604901?5??8 ???548?742149?6???810?60?63?4?48?35??5032?1?63?330 ?2626175??010811510??5?570?4???4719??78226?5438809 1332040189157?46388??1961?176?77?11?8?0...
output:
913581097
result:
ok 1 number(s): "913581097"
Test #51:
score: 0
Accepted
time: 36ms
memory: 18892kb
input:
50 50 02?0??67306??228833?10425685289996?38131??06111150 ???5338459437770?1160454385626349?088???2709904811 ?358309?43067857774996427155144?5402716613?7101?08 1066067?5172?7?1?1941098?458?22?7525768224?52???53 1359935009425163480954?6760??4495809902510?40?963? ?378672?696925?0?70?5?925352263684?2688...
output:
454658329
result:
ok 1 number(s): "454658329"
Test #52:
score: 0
Accepted
time: 245ms
memory: 18876kb
input:
50 50 ????????????????????????????????4????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ???????????????????????????????????????...
output:
136998761
result:
ok 1 number(s): "136998761"
Test #53:
score: 0
Accepted
time: 240ms
memory: 18900kb
input:
50 50 ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ?????????????????????????????????????????????????? ???????????????????????????????????????...
output:
564071240
result:
ok 1 number(s): "564071240"
Test #54:
score: 0
Accepted
time: 34ms
memory: 18880kb
input:
50 50 03887126663007067971362875340843831423377201714531 05941508836659209975229528627364167944196991552144 13379796300726573301501397816844474131798821542728 18610331756265877746645641719453123282222850374392 21651242668814092190894932647801215330392024380650 216989323857609919665101768593491326566...
output:
748137777
result:
ok 1 number(s): "748137777"
Test #55:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
1 1 ?
output:
45
result:
ok 1 number(s): "45"
Test #56:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #57:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
1 1 0
output:
0
result:
ok 1 number(s): "0"
Test #58:
score: 0
Accepted
time: 0ms
memory: 3348kb
input:
1 1 5
output:
5
result:
ok 1 number(s): "5"
Test #59:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
10 1 9 8 7 6 5 4 3 2 1 0
output:
0
result:
ok 1 number(s): "0"
Test #60:
score: 0
Accepted
time: 0ms
memory: 3376kb
input:
5 3 999 ??? ??? ??? ???
output:
0
result:
ok 1 number(s): "0"
Test #61:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
3 3 3?8 ?1? 4??
output:
11528550
result:
ok 1 number(s): "11528550"
Test #62:
score: 0
Accepted
time: 2ms
memory: 3424kb
input:
3 3 998 9?? 999
output:
0
result:
ok 1 number(s): "0"
Test #63:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
3 3 997 ??? 999
output:
2994
result:
ok 1 number(s): "2994"