Submission #794709

#TimeUsernameProblemLanguageResultExecution timeMemory
794709baneJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
2 ms468 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(i); monsters[i] = {b,p}; } vector<int>dp(m, (int)1e9); dp[0] = 0; priority_queue<pair<int,int>>pq; pq.push({0,0}); while(!pq.empty()){ int dst = -pq.top().first; int node = pq.top().second; pq.pop(); //node + pow * x = mn if (dp[node] != dst)continue; if (node == 1){ cout << dst << endl; return ; } int p = monsters[node].second; int b = monsters[node].first; for (int i = 1; i <= n / p; i++){ int right = b + i * p; int left = b - i * p; if (left >= 0){ for (int j : pos[left]){ if (dp[j] > dst + i){ dp[j] = dst + i; pq.push({-dp[j], j}); } } } if (right <= n - 1){ for (int j : pos[right]){ if (dp[j] > dst + i){ dp[j] = dst + i; pq.push({-dp[j], j}); } } } } } assert(false); } 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...