#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e15;
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int m, n; cin >> m >> n;
vector<int> a(n), b(n), dp(n);
for(int &p : dp) p=INF;
for(int i=0; i<n; i++) cin >> a[i] >> b[i];
for(int KALI=0; KALI<n; KALI++) {
for(int i=0; i<n; i++) {
if(abs(a[i]-a[1])%b[i]==0) dp[i]=min(dp[i], abs(a[i]-a[1])/b[i]);
for(int j=0; j<n; j++) {
if(i==j) continue;
if(abs(a[i]-a[j])%b[i]) continue;
dp[i]=min(dp[i], dp[j]+abs(a[i]-a[j])/b[i]);
}
}
}
cout << dp[0] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |