제출 #794739

#제출 시각아이디문제언어결과실행 시간메모리
794739baneJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1080 ms4560 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") void solve(){ int n, m; cin >> n >> m; vector<pair<int,int>>monsters(m); vector<vector<int>>pos(n); for (int i = 0; i < m; i++){ int b, p; cin >> b >> p; pos[b].push_back(p); monsters[i] = {b,p}; } vector<long long>dp(n, (long long)1e18); dp[monsters[0].first] = 0; priority_queue<pair<long long,int>>pq; pq.push({0,monsters[0].first}); while(!pq.empty()){ long long dst = -pq.top().first; int b = pq.top().second; pq.pop(); //node + pow * x = mn if (dp[b] != dst)continue; if (b == monsters[1].first){ cout << dst << endl; return ; } for (auto p : pos[b]){ for (int i = 1; i <= n / p; i++){ int right = b + i * p; int left = b - i * p; if (left >= 0){ if (dp[left] > dst + i){ dp[left] = dst + i; pq.push({-dst-i,left}); } } if (right <= n - 1){ if (dp[right] > dst + i){ dp[right] = dst + i; pq.push({-dst-i,right}); } } } } } cout << - 1 << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); 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...