제출 #707087

#제출 시각아이디문제언어결과실행 시간메모리
707087600MihneaJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms324 KiB
#include <cmath> #include <functional> #include <fstream> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <cassert> #include <bitset> #include <sstream> #include <chrono> #include <cstring> #include <numeric> using namespace std; const int INF = (int)1e9 + 7; struct T { int pos; int delta; }; signed main() { #ifdef ONPC FILE* stream; freopen_s(&stream, "input.txt", "r", stdin); #else ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif int dim, cntofs; cin >> dim >> cntofs; vector<T> ofs(cntofs); for (auto& of : ofs) { cin >> of.pos >> of.delta; assert(0 <= of.pos && of.pos < dim); } vector<int> dp(cntofs, INF); priority_queue<pair<int, int>> pq; auto relax = [&](int i, int val) { if (val < dp[i]) { dp[i] = val; pq.push({ -dp[i], i }); } }; relax(0, 0); while (!pq.empty()) { auto it = pq.top(); pq.pop(); int i = it.second; if (-it.first != dp[i]) { continue; } for (int j = 0; j < cntofs; j++) { int posdif = abs(ofs[i].pos - ofs[j].pos); if (posdif % ofs[i].delta==0) { relax(j, dp[i] + posdif / ofs[i].delta); } } } cout << dp[1] << "\n"; 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...