Submission #68443

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x), end(x)
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int_fast64_t lINF = 0x3f3f3f3f3f3f3f3fll;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
template <class Func>
class FixPoint : Func {
public:
explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
template <class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
return FixPoint<Func>{forward<Func>(f)};
}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> inline void bye(T x) { cout << x << '\n'; exit(0); }
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int m, r;
cin >> m >> r;
vector<pair<int, int> > pos = {
{0, 0},
{1, 0}, {1, 1}, {1, 2},
{2, 0}, {2, 1}, {2, 2},
{3, 0}, {3, 1}, {3, 2}
};
vector<vector<int> > dist(10, vector<int>(10));
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < 10; ++j) {
dist[i][j] = abs(pos[i].first - pos[j].first) + abs(pos[i].second - pos[j].second);
}
}
vector<vector<int> > min_cost(m, vector<int>(10, INF));
min_heap<tuple<int, int, int> > que;
min_cost[0][0] = 0;
que.emplace(0, 0, 0);
while (!que.empty()) {
auto [cur_cost, mod, cur_node] = que.top();
que.pop();
if (min_cost[mod][cur_node] < cur_cost) continue;
for (int i = 0; i < 10; ++i) {
if (chmin(min_cost[(mod * 10 + i) % m][i], min_cost[mod][cur_node] + dist[cur_node][i] + 1)) {
que.emplace(min_cost[(mod * 10 + i) % m][i], (mod * 10 + i) % m, i);
}
}
}
cout << *min_element(all(min_cost[r])) << '\n';
return (0);
}

ステータス

項目 データ
問題 1268 - テンキー (Tenkey)
ユーザー名 ei1903
投稿日時 2021-09-15 16:23:43
言語 C++17
状態 Accepted
得点 100
ソースコード長 2744 Byte
最大実行時間 443 ms
最大メモリ使用量 38024 KB

セット

セット 得点 Cases
1 Subtask1 30 / 30 sample*, 01*
2 Subtask2 70 / 70 sample*, 01*, 02*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt AC 64 ms 14036 KB
1
2
01-02.txt AC 72 ms 13828 KB
1
2
01-03.txt AC 68 ms 13748 KB
1
2
01-04.txt AC 65 ms 13928 KB
1
2
01-05.txt AC 62 ms 13848 KB
1
2
01-06.txt AC 61 ms 14024 KB
1
2
01-07.txt AC 68 ms 13952 KB
1
2
01-08.txt AC 60 ms 14000 KB
1
2
01-09.txt AC 62 ms 14052 KB
1
2
01-10.txt AC 64 ms 14104 KB
1
2
01-11.txt AC 65 ms 14024 KB
1
2
01-12.txt AC 65 ms 13952 KB
1
2
01-13.txt AC 64 ms 14004 KB
1
2
01-14.txt AC 70 ms 14052 KB
1
2
02-01.txt AC 20 ms 544 KB
2
02-02.txt AC 31 ms 1200 KB
2
02-03.txt AC 15 ms 760 KB
2
02-04.txt AC 17 ms 780 KB
2
02-05.txt AC 18 ms 832 KB
2
02-06.txt AC 19 ms 840 KB
2
02-07.txt AC 64 ms 15172 KB
2
02-08.txt AC 261 ms 33148 KB
2
02-09.txt AC 113 ms 18624 KB
2
02-10.txt AC 297 ms 33268 KB
2
02-11.txt AC 71 ms 10640 KB
2
02-12.txt AC 25 ms 3964 KB
2
02-13.txt AC 366 ms 35468 KB
2
02-14.txt AC 373 ms 35452 KB
2
02-15.txt AC 54 ms 4812 KB
2
02-16.txt AC 214 ms 24332 KB
2
02-17.txt AC 65 ms 6576 KB
2
02-18.txt AC 166 ms 19528 KB
2
02-19.txt AC 242 ms 26468 KB
2
02-20.txt AC 443 ms 37452 KB
2
02-21.txt AC 234 ms 24828 KB
2
02-22.txt AC 21 ms 972 KB
2
02-23.txt AC 27 ms 1252 KB
2
02-24.txt AC 243 ms 26008 KB
2
02-25.txt AC 440 ms 36864 KB
2
02-26.txt AC 427 ms 38024 KB
2
02-27.txt AC 228 ms 26392 KB
2
02-28.txt AC 224 ms 25732 KB
2
02-29.txt AC 418 ms 37692 KB
2
02-30.txt AC 227 ms 25924 KB
2
02-31.txt AC 70 ms 14876 KB
2
02-32.txt AC 218 ms 24672 KB
2
02-33.txt AC 62 ms 13580 KB
2
02-34.txt AC 64 ms 12680 KB
2
02-35.txt AC 61 ms 13572 KB
2
sample-01.txt AC 64 ms 14204 KB
1
2
sample-02.txt AC 21 ms 828 KB
1
2