Advertisement
skaram

Untitled

Dec 17th, 2022
863
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. //// @author s_k_a_r_a
  2.  
  3. #ifdef Local
  4. #include "debug.h"
  5. #else
  6. // #pragma GCC optimize("Ofast")
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #define debug(...)
  10. #endif
  11.  
  12. #define int long long
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. #define vec vector
  18. #define str string
  19. #define all(x) (x).begin(), (x).end()
  20. #define rall(x) (x).rbegin(), (x).rend()
  21. #define sz(x) (int)(x).size()
  22. #define pb push_back
  23.  
  24. using namespace std;
  25.  
  26. void solve() {
  27.     int n, a, b, c;
  28.     cin >> n >> a >> b >> c;
  29.     if (n == 1) {
  30.         cout << 1;
  31.         return;
  32.     }
  33.     if (a > b)
  34.         swap(a, b);
  35.     if (a > c)
  36.         swap(a, c);
  37.     if (b > c)
  38.         swap(b, c);
  39.     if (a == 1) {
  40.         cout << n;
  41.         return;
  42.     }
  43.     priority_queue<pair<int, int>> pq;
  44.     pq.push({0, 1});
  45.     vec<int> dist(a, n + 1);
  46.     dist[1] = 0;
  47.     vec<int> used(a);
  48.     for (int v; !pq.empty();) {
  49.         v = pq.top().second;
  50.         pq.pop();
  51.         if (used[v])
  52.             continue;
  53.         used[v] = 1;
  54.         if (dist[(v + b) % a] > dist[v] + b)
  55.             dist[(v + b) % a] = dist[v] + b, pq.push({-(dist[v] + b), (v + b) % a});
  56.         if (dist[(v + c) % a] > dist[v] + c)
  57.             dist[(v + c) % a] = dist[v] + c, pq.push({-(dist[v] + c), (v + c) % a});
  58.     }
  59.     debug(dist);
  60.     int ans = 0;
  61.     for (int k = 0; k < a; k++) {
  62.         if (n - dist[k] - 1 >= 0)
  63.             ans += (n - dist[k] - 1) / a + 1;
  64.         debug((n - dist[k] - 1) / a + 1);
  65.     }
  66.     debug(ans);
  67.     cout << ans;
  68. }
  69.  
  70. signed main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.  
  74.     int tt = 1;
  75.     //    cin >> tt;
  76.     while (tt--)
  77.         solve();
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement