Submission #1193352

#TimeUsernameProblemLanguageResultExecution timeMemory
1193352zyadhanySirni (COCI17_sirni)C++20
0 / 140
793 ms47464 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> #define ll int #define ld long double #define pl pair<ll, ll> #define vi vector<ll> #define vii vector<vi> #define vc vector<char> #define vcc vector<vc> #define vp vector<pl> #define mi map<ll,ll> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define all(X) X.begin(),X.end() #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "YES\n"; return;} #define NO {cout << "NO\n"; return;} #define MUN {cout << "-1\n"; return;} const int MODE = 1e9 + 7; using namespace std; void solve(int tc) { ll n; cin >> n; vi X(n); for (int i = 0; i < n; i++) { cin >> X[i]; } set st(all(X)); X.assign(all(st)); n = X.size(); priority_queue<vi, vector<vi>, greater<vi>> pq; vector<bool> visited(n + 1, false); ll res = 0; pq.push({0, 0, 0}); while(!pq.empty()){ auto p = pq.top(); pq.pop(); int wt = p[0]; int u = p[2]; if(visited[u]) continue; res += wt; visited[u] = true; for (int j = X[u]; j <= X.back(); j+=X[u]) { ll re = lower_bound(all(X), j) - X.begin(); re += (j == X[u]); if (re < X.size() && X[re] < j + X[u]) { if(!visited[re]) pq.push({X[re]%X[u], u, re}); } } } cout << res << '\n'; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; // freopen("math.in", "r", stdin); //freopen("output.txt", "w", stdout); // cin >> size; for (int i = 1; i <= size; i++) solve(i); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...