Submission #1262702

#TimeUsernameProblemLanguageResultExecution timeMemory
1262702tormentJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
129 ms32072 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2005; const long long inf = 1e18; long long G[N][N], dist[N]; bool used[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i = 0;i < n;++i){ for(int j = 0;j < n;++j){ G[i][j] = inf; } G[i][i] = 0; dist[i] = inf; } vector<array<int, 2>>v(m); for(int i = 0;i < m;++i){ int b, p; cin >> b >> p; v[i] = {b, p}; for(int j = b;j < n;j += p){ long long w = (j - b) / p; G[b][j] = min(G[b][j], w); } for(int j = b;j >= 0;j -= p){ long long w = (b - j) / p; G[b][j] = min(G[b][j], w); } } int s = v[0][0], t = v[1][0]; dist[s] = 0; while(true){ int mn = -1; for(int i = 0;i < n;++i){ if(used[i])continue; if(mn == -1 || dist[mn] > dist[i])mn = i; } if(mn == -1)break; used[mn] = true; for(int i = 0;i < n;++i){ if(G[mn][i] != inf){ dist[i] = min(dist[i], dist[mn] + G[mn][i]); } } } if(dist[t] == inf)dist[t] = -1; cout << dist[t] << '\n'; }
#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...