Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //// @author s_k_a_r_a
- #ifdef Local
- #include "debug.h"
- #else
- // #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #define debug(...)
- #endif
- #define int long long
- typedef long long ll;
- typedef long double ld;
- #define vec vector
- #define str string
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define sz(x) (int)(x).size()
- #define pb push_back
- using namespace std;
- void solve() {
- int n, a, b, c;
- cin >> n >> a >> b >> c;
- if (n == 1) {
- cout << 1;
- return;
- }
- if (a > b)
- swap(a, b);
- if (a > c)
- swap(a, c);
- if (b > c)
- swap(b, c);
- if (a == 1) {
- cout << n;
- return;
- }
- priority_queue<pair<int, int>> pq;
- pq.push({0, 1});
- vec<int> dist(a, n + 1);
- dist[1] = 0;
- vec<int> used(a);
- for (int v; !pq.empty();) {
- v = pq.top().second;
- pq.pop();
- if (used[v])
- continue;
- used[v] = 1;
- if (dist[(v + b) % a] > dist[v] + b)
- dist[(v + b) % a] = dist[v] + b, pq.push({-(dist[v] + b), (v + b) % a});
- if (dist[(v + c) % a] > dist[v] + c)
- dist[(v + c) % a] = dist[v] + c, pq.push({-(dist[v] + c), (v + c) % a});
- }
- debug(dist);
- int ans = 0;
- for (int k = 0; k < a; k++) {
- if (n - dist[k] - 1 >= 0)
- ans += (n - dist[k] - 1) / a + 1;
- debug((n - dist[k] - 1) / a + 1);
- }
- debug(ans);
- cout << ans;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int tt = 1;
- // cin >> tt;
- while (tt--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement