제출 #794743

#제출 시각아이디문제언어결과실행 시간메모리
794743baneJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1096 ms5704 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<set<int>>pos(n); for (int i = 0; i < m; i++){ int b, p; cin >> b >> p; pos[b].insert(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 ; } if (pos[b].empty())continue; int pmin = *pos[b].begin(); for (int i = 1; i <= n / pmin; i++){ for (auto p : pos[b]){ bool ok = 0; int right = b + i * p; int left = b - i * p; if (left >= 0){ ok = 1; if (dp[left] > dst + i){ dp[left] = dst + i; pq.push({-dst-i,left}); } } if (right <= n - 1){ ok = 1; if (dp[right] > dst + i){ dp[right] = dst + i; pq.push({-dst-i,right}); } } if (!ok)break; } } } 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...