제출 #707093

#제출 시각아이디문제언어결과실행 시간메모리
707093600MihneaJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1070 ms7672 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); vector<vector<int>> cine(dim); for (int i = 0; i < cntofs; i++) { cin >> ofs[i].pos >> ofs[i].delta; assert(0 <= ofs[i].pos && ofs[i].pos < dim); cine[ofs[i].pos].push_back(i); } vector<int> dp(dim, 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 }); } }; set<pair<int, int>> s_delta_rest; // {delta, rest} for (auto& it : ofs) { s_delta_rest.insert({ it.delta, it.pos % it.delta }); } vector<pair<int, int>> v_delta_rest; for (auto& it : s_delta_rest) { v_delta_rest.push_back(it); } int states = (int)v_delta_rest.size(); vector<vector<int>> cool(states); for (int it = 0; it < states; it++) { int i = v_delta_rest[it].first, j = v_delta_rest[it].second; for (int p = j; p < dim; p += i) { if (!cine[p].empty()) { cool[it].push_back(p); } } } auto fnd = [&](pair<int, int> it) { assert(0 <= it.second && it.second < it.first); int l = 0, r = (int)v_delta_rest.size() - 1; while (l <= r) { int m = (l + r) / 2; if (v_delta_rest[m] == it) { return m; } if (v_delta_rest[m] < it) { l = m + 1; } else { r = m - 1; } } assert(0); }; relax(ofs[0].pos, 0); while (!pq.empty()) { auto it = pq.top(); pq.pop(); int loc = it.second; if (-it.first != dp[loc]) { continue; } for (auto& i : cine[loc]) { for (auto& loc2 : cool[fnd({ ofs[i].delta, loc % ofs[i].delta })]) { int posdif = abs(ofs[i].pos - loc2); relax(loc2, dp[loc] + posdif / ofs[i].delta); } } } int sol = (dp[ofs[1].pos] == INF) ? (-1) : (dp[ofs[1].pos]); cout << sol << "\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...