제출 #676874

#제출 시각아이디문제언어결과실행 시간메모리
676874ArnchJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
15 ms23944 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ /* link: */ #include<bits/stdc++.h> //#pragma GCC optimize("O3,no-stack-protector,unroll-loops") //#pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl #define mak make_pair //constexpr int PRI = 1000696969; constexpr ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7; int b[N], x[N]; ll d[N]; vector<int> vc[N]; int main() { ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0); int n, m; cin >>n >>m; for(int i = 0; i < m; i++) { cin >>b[i] >>x[i]; vc[b[i]].push_back(i); } for(int i = 0; i < n; i++) d[i] = INF; d[b[0]] = 0; set<pair<ll, int> > st; st.insert({0, b[0]}); while(!st.empty()) { int p = st.begin() -> second; st.erase(st.begin()); if(p == x[1]) { return cout<<d[p], 0; } for(auto j : vc[p]) { for(int cnt = 1; p + cnt * x[j] < n; cnt++) { int pq = p + cnt * x[j]; if(d[p] + cnt < d[pq]) { st.erase({d[pq], pq}); d[pq] = d[p] + cnt; st.insert({d[pq], pq}); } } for(int cnt = 1; p - cnt * x[j] >= 0; cnt++) { int pq = p - cnt * x[j]; if(d[p] + cnt < d[pq]) { st.erase({d[pq], pq}); d[pq] = d[p] + cnt; st.insert({d[pq], pq}); } } } } cout<<-1; return 0; }
#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...