제출 #1130628

#제출 시각아이디문제언어결과실행 시간메모리
1130628am_aadvikJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
1096 ms836 KiB
#include <iostream> #include<vector> #include<string> #include<queue> #include<map> #include<set> #include<algorithm> #include<math.h> const int inf = 1e9; const int maxn = 300005; const int mod = (int)1e9 + 7; using namespace std; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<pair<int, int>> d; vector<int> ans(n + 1, inf); for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; if (i == 1) ans[x] = 0; d.push_back({ x, y }); } for (int i = 0; i < m; ++i) if (!(abs(d[i].first - d[1].first) % d[i].second)) ans[d[i].first] = abs(d[i].first - d[1].first) / d[i].second; bool c = 1; for (int j = 0; ((j < n) && c); ++j) { c = 0; for (auto x : d) { for (int i = x.first, val = 0; i >= 0; i -= x.second, ++val) if (ans[x.first] > (ans[i] + val)) ans[x.first] = ans[i] + val, c = 1; for (int i = x.first, val = 0; i < n; i += x.second, ++val) if (ans[x.first] > (ans[i] + val)) ans[x.first] = ans[i] + val, c = 1; } } cout << ((ans[d[0].first] == inf) ? -1 : ans[d[0].first]); }
#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...