Submission #1191001

#TimeUsernameProblemLanguageResultExecution timeMemory
1191001ulvixSirni (COCI17_sirni)C++20
42 / 140
5095 ms1864 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define all(x) x.begin(),x.end() const ll sz=1e5+100; const ll mod=1e9+7; const ll INF=1e18; using namespace std; using namespace __gnu_pbds; template<class T> using indexed_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll n; cin>>n; vector<ll> v(n); for(ll i=0;i<n;i++){ cin>>v[i]; } vector<bool> b(n); vector<ll> mns(n,INF); mns[0]=0; ll ans=0; for(ll i=0;i<n;i++){ ll best=INF; ll bestt=-1; for(ll j=0;j<n;j++){ if(!b[j] && mns[j]<best){ best=mns[j]; bestt=j; } } b[bestt]=1; ans+=best; for(ll j=0;j<n;j++){ if(b[j]) continue; ll a=min(v[bestt]%v[j],v[j]%v[bestt]); if(a<mns[j]){ mns[j]=a; } } } cout<<ans; }
#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...