結果
問題 | No.1465 Archaea |
ユーザー | tabae326 |
提出日時 | 2021-04-02 22:52:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 1,308 bytes |
コンパイル時間 | 2,398 ms |
コンパイル使用メモリ | 211,080 KB |
実行使用メモリ | 41,224 KB |
最終ジャッジ日時 | 2023-08-25 16:20:06 |
合計ジャッジ時間 | 3,700 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 21 ms
12,304 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 33 ms
17,508 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 28 ms
14,956 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 67 ms
32,264 KB |
testcase_14 | AC | 30 ms
15,732 KB |
testcase_15 | AC | 2 ms
4,380 KB |
testcase_16 | AC | 3 ms
4,376 KB |
testcase_17 | AC | 74 ms
33,528 KB |
testcase_18 | AC | 6 ms
5,180 KB |
testcase_19 | AC | 33 ms
16,868 KB |
testcase_20 | AC | 52 ms
25,676 KB |
testcase_21 | AC | 91 ms
41,184 KB |
testcase_22 | AC | 90 ms
41,224 KB |
testcase_23 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++) void dijkstra(vector<vector<pair<ll,ll>>> G, vector<ll> &d, ll srt){ priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> que; que.push({0, srt}); d[srt] = 0; while(!que.empty()){ auto q = que.top(); que.pop(); if(q.first > d[q.second]) continue; for(auto g : G[q.second]){ if(d[g.first] <= q.first + g.second) continue; d[g.first] = q.first + g.second; que.push({d[g.first], g.first}); } } } void dijkstra(vector<vector<ll>>& G, vector<ll> &d, ll srt) { ll n = G.size(); vector<vector<pair<ll,ll>>> P(n); rep(i, 0, n) { for(auto j : G[i]) P[i].push_back({j, 1}); } dijkstra(P, d, srt); } void solve() { ll n, k; cin >> n >> k; const ll inf = 1e18; vector<ll> dp(n+1, inf); vector<vector<ll>> G(n+1); rep(i, 1, n+1) { if(i+3 <= n) G[i].push_back(i+3); if(i*2 <= n) G[i].push_back(2*i); } dijkstra(G, dp, 1); if(dp[n] <= k) cout << "YES\n"; else cout << "NO\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }