#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 3e3+20,mod = 1e9+7,inf = 1e9,sq = 400;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int n,ll k){
int c = 1;
while (k){
if (k&1) c = (1ll*c*n)%mod;
n = (1ll*n*n)%mod;
k >>= 1;
}
return c;
}
int e[N][N],d[N];
int n,a[N],p[N];
inline void dij(){
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push({0,a[0]});
d[a[0]] = 0;
while (!pq.empty()){
pll p = pq.top();
int y = p.Y;
pq.pop();
rep(i,0,n){
if (d[i] > d[y] && d[i]-d[y] > e[y][i]){
d[i] = d[y]+e[y][i];
pq.push({d[i],i});
}
}
}
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(e,127,sizeof e);
memset(d,127,sizeof d);
ll Inf = d[0];
int m;
cin >> n >> m;
rep(i,0,m){
cin >> a[i] >> p[i];
if (i == 1) continue;
int x = a[i];
int t = 0;
while (x < n){
e[a[i]][x] = min(e[a[i]][x],t);
x += p[i];
t++;
}
x = a[i]-p[i];
t = 1;
while (x >= 0){
e[a[i]][x] = min(e[a[i]][x],t);
t++;
x -= p[i];
}
}
dij();
if (d[a[1]] >= Inf) cout << -1;
else
cout << d[a[1]];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35916 KB |
Output is correct |
2 |
Correct |
18 ms |
35916 KB |
Output is correct |
3 |
Correct |
17 ms |
35920 KB |
Output is correct |
4 |
Correct |
15 ms |
35916 KB |
Output is correct |
5 |
Correct |
14 ms |
35916 KB |
Output is correct |
6 |
Correct |
17 ms |
35916 KB |
Output is correct |
7 |
Correct |
14 ms |
35916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35912 KB |
Output is correct |
2 |
Correct |
15 ms |
35916 KB |
Output is correct |
3 |
Correct |
15 ms |
35964 KB |
Output is correct |
4 |
Correct |
16 ms |
35916 KB |
Output is correct |
5 |
Correct |
16 ms |
36008 KB |
Output is correct |
6 |
Correct |
17 ms |
35916 KB |
Output is correct |
7 |
Correct |
17 ms |
35916 KB |
Output is correct |
8 |
Correct |
15 ms |
35900 KB |
Output is correct |
9 |
Correct |
16 ms |
35968 KB |
Output is correct |
10 |
Correct |
17 ms |
35944 KB |
Output is correct |
11 |
Correct |
18 ms |
36044 KB |
Output is correct |
12 |
Correct |
19 ms |
36044 KB |
Output is correct |
13 |
Correct |
17 ms |
36044 KB |
Output is correct |
14 |
Correct |
17 ms |
36028 KB |
Output is correct |
15 |
Correct |
17 ms |
36044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35980 KB |
Output is correct |
2 |
Correct |
14 ms |
35916 KB |
Output is correct |
3 |
Correct |
15 ms |
35952 KB |
Output is correct |
4 |
Correct |
15 ms |
35928 KB |
Output is correct |
5 |
Correct |
16 ms |
35932 KB |
Output is correct |
6 |
Correct |
15 ms |
35932 KB |
Output is correct |
7 |
Correct |
15 ms |
35984 KB |
Output is correct |
8 |
Correct |
17 ms |
35916 KB |
Output is correct |
9 |
Correct |
16 ms |
35968 KB |
Output is correct |
10 |
Correct |
15 ms |
35956 KB |
Output is correct |
11 |
Correct |
15 ms |
36044 KB |
Output is correct |
12 |
Correct |
20 ms |
36024 KB |
Output is correct |
13 |
Correct |
16 ms |
36028 KB |
Output is correct |
14 |
Correct |
17 ms |
35988 KB |
Output is correct |
15 |
Correct |
15 ms |
36044 KB |
Output is correct |
16 |
Correct |
16 ms |
36000 KB |
Output is correct |
17 |
Correct |
19 ms |
36080 KB |
Output is correct |
18 |
Correct |
15 ms |
36044 KB |
Output is correct |
19 |
Correct |
15 ms |
35916 KB |
Output is correct |
20 |
Correct |
23 ms |
36040 KB |
Output is correct |
21 |
Correct |
15 ms |
35972 KB |
Output is correct |
22 |
Correct |
15 ms |
35940 KB |
Output is correct |
23 |
Correct |
21 ms |
35960 KB |
Output is correct |
24 |
Correct |
27 ms |
36044 KB |
Output is correct |
25 |
Correct |
24 ms |
36052 KB |
Output is correct |
26 |
Correct |
23 ms |
35996 KB |
Output is correct |
27 |
Correct |
22 ms |
35940 KB |
Output is correct |
28 |
Correct |
23 ms |
36060 KB |
Output is correct |
29 |
Correct |
28 ms |
36156 KB |
Output is correct |
30 |
Correct |
24 ms |
36044 KB |
Output is correct |
31 |
Correct |
26 ms |
36144 KB |
Output is correct |
32 |
Correct |
25 ms |
36096 KB |
Output is correct |
33 |
Correct |
28 ms |
36176 KB |
Output is correct |
34 |
Correct |
27 ms |
36172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
35916 KB |
Output is correct |
2 |
Correct |
19 ms |
35920 KB |
Output is correct |
3 |
Correct |
15 ms |
35928 KB |
Output is correct |
4 |
Correct |
15 ms |
35964 KB |
Output is correct |
5 |
Correct |
15 ms |
36012 KB |
Output is correct |
6 |
Correct |
16 ms |
35916 KB |
Output is correct |
7 |
Correct |
18 ms |
35916 KB |
Output is correct |
8 |
Correct |
15 ms |
35916 KB |
Output is correct |
9 |
Correct |
15 ms |
35916 KB |
Output is correct |
10 |
Correct |
18 ms |
36040 KB |
Output is correct |
11 |
Correct |
16 ms |
36044 KB |
Output is correct |
12 |
Correct |
16 ms |
35976 KB |
Output is correct |
13 |
Correct |
15 ms |
36044 KB |
Output is correct |
14 |
Correct |
15 ms |
35980 KB |
Output is correct |
15 |
Correct |
15 ms |
36028 KB |
Output is correct |
16 |
Correct |
16 ms |
36024 KB |
Output is correct |
17 |
Correct |
18 ms |
36040 KB |
Output is correct |
18 |
Correct |
15 ms |
36044 KB |
Output is correct |
19 |
Correct |
15 ms |
35916 KB |
Output is correct |
20 |
Correct |
23 ms |
36044 KB |
Output is correct |
21 |
Correct |
15 ms |
36040 KB |
Output is correct |
22 |
Correct |
18 ms |
35980 KB |
Output is correct |
23 |
Correct |
25 ms |
36044 KB |
Output is correct |
24 |
Correct |
28 ms |
36068 KB |
Output is correct |
25 |
Correct |
25 ms |
36044 KB |
Output is correct |
26 |
Correct |
23 ms |
36064 KB |
Output is correct |
27 |
Correct |
21 ms |
36048 KB |
Output is correct |
28 |
Correct |
21 ms |
36044 KB |
Output is correct |
29 |
Correct |
28 ms |
36044 KB |
Output is correct |
30 |
Correct |
24 ms |
36032 KB |
Output is correct |
31 |
Correct |
26 ms |
36144 KB |
Output is correct |
32 |
Correct |
25 ms |
36108 KB |
Output is correct |
33 |
Correct |
29 ms |
36056 KB |
Output is correct |
34 |
Correct |
28 ms |
36164 KB |
Output is correct |
35 |
Incorrect |
25 ms |
36036 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35916 KB |
Output is correct |
2 |
Correct |
15 ms |
35984 KB |
Output is correct |
3 |
Correct |
15 ms |
35916 KB |
Output is correct |
4 |
Correct |
15 ms |
35916 KB |
Output is correct |
5 |
Correct |
16 ms |
35980 KB |
Output is correct |
6 |
Correct |
15 ms |
35920 KB |
Output is correct |
7 |
Correct |
15 ms |
35956 KB |
Output is correct |
8 |
Correct |
16 ms |
35916 KB |
Output is correct |
9 |
Correct |
15 ms |
35916 KB |
Output is correct |
10 |
Correct |
15 ms |
35944 KB |
Output is correct |
11 |
Correct |
15 ms |
36012 KB |
Output is correct |
12 |
Correct |
15 ms |
36028 KB |
Output is correct |
13 |
Correct |
15 ms |
36044 KB |
Output is correct |
14 |
Correct |
16 ms |
35936 KB |
Output is correct |
15 |
Correct |
15 ms |
35964 KB |
Output is correct |
16 |
Correct |
16 ms |
35996 KB |
Output is correct |
17 |
Correct |
18 ms |
36068 KB |
Output is correct |
18 |
Correct |
16 ms |
36044 KB |
Output is correct |
19 |
Correct |
15 ms |
35916 KB |
Output is correct |
20 |
Correct |
27 ms |
36028 KB |
Output is correct |
21 |
Correct |
16 ms |
36044 KB |
Output is correct |
22 |
Correct |
16 ms |
36016 KB |
Output is correct |
23 |
Correct |
22 ms |
36020 KB |
Output is correct |
24 |
Correct |
27 ms |
36080 KB |
Output is correct |
25 |
Correct |
24 ms |
36080 KB |
Output is correct |
26 |
Correct |
23 ms |
36040 KB |
Output is correct |
27 |
Correct |
22 ms |
36004 KB |
Output is correct |
28 |
Correct |
22 ms |
35928 KB |
Output is correct |
29 |
Correct |
28 ms |
36164 KB |
Output is correct |
30 |
Correct |
25 ms |
36128 KB |
Output is correct |
31 |
Correct |
25 ms |
36116 KB |
Output is correct |
32 |
Correct |
24 ms |
36096 KB |
Output is correct |
33 |
Correct |
28 ms |
36172 KB |
Output is correct |
34 |
Correct |
30 ms |
36200 KB |
Output is correct |
35 |
Incorrect |
26 ms |
36044 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |