#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int long long
#define pii pair<int, int>
#define ld long double
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e18 + 9;
const int MAX = 3e4 + 6;
int MOD = 998244353;
int n, m;
map<int, int> dp[MAX];
vector<int> arr[MAX];
pii d0, d1;
int rec(int i, int p){
if(d1.first == i) return 0;
if(dp[i].count(p)) return dp[i][p];
dp[i][p] = oo;
int ans = oo;
if(i - p >= 0){
ans = min(ans, rec(i - p, p) + 1);
for(int a : arr[i - p]){
ans = min(ans, rec(i - p, a) + 1);
}
}
if(i + p < n){
ans = min(ans, rec(i + p, p) + 1);
for(int a : arr[i + p]){
ans = min(ans, rec(i + p, a) + 1);
}
}
return dp[i][p] = ans;
}
void solve(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, p; cin >> x >> p;
if(!i) d0 = {x, p};
if(i==1) d1 = {x, p};
arr[x].push_back(p);
}
cout << rec(d0.first, d0.second) << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |