Submission #1075961

#TimeUsernameProblemLanguageResultExecution timeMemory
1075961alexddJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
744 ms3800 KiB
#include<bits/stdc++.h> using namespace std; const int INF = 1e9; int n,m; int b[30005],p[30005]; int dist[300005]; priority_queue<pair<int,int>> pq; vector<int> onpoz[30005]; signed main() { cin>>n>>m; for(int i=0;i<n;i++) dist[i]=INF; for(int i=0;i<m;i++) { cin>>b[i]>>p[i]; onpoz[b[i]].push_back(i); } dist[b[0]]=0; pq.push({0,b[0]}); while(!pq.empty()) { int cdist = -pq.top().first; int poz = pq.top().second; pq.pop(); if(dist[poz]!=cdist) continue; for(int id:onpoz[poz]) { assert(b[id]==poz); for(int i=1;poz+i*p[id]<n;i++) { int cpoz = poz+i*p[id]; if(dist[cpoz] > dist[poz]+i) { dist[cpoz] = dist[poz]+i; pq.push({-dist[cpoz],cpoz}); } } for(int i=1;poz-i*p[id]>=0;i++) { int cpoz = poz-i*p[id]; if(dist[cpoz] > dist[poz]+i) { dist[cpoz] = dist[poz]+i; pq.push({-dist[cpoz],cpoz}); } } } } if(dist[b[1]]==INF) cout<<-1; else cout<<dist[b[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...