//#define _GLIBCXX_DEBUG
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
int bit(int x, int b) {
return (x >> b) & 1;
}
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 30002, B = 100;
const int mod = 998244353;
const ld eps = 1e-9;
int dist[B][N], S[N], P[N];
bool used[B][N];
vector<array<int, 3>> adj[B][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> S[i] >> P[i];
if (P[i] < B) {
adj[0][S[i]].push_back({0, P[i], S[i]});
} else {
for (int w = 1; P[i] * w + S[i] < n; ++w) {
adj[0][S[i]].push_back({w, 0, P[i] * w + S[i]});
}
for (int w = -1; P[i] * w + S[i] > -1; --w) {
adj[0][S[i]].push_back({-w, 0, P[i] * w + S[i]});
}
}
}
normal_queue<array<int, 3>> pq;
auto add = [&pq](int w, int i, int j) {
if (dist[i][j] > w) {
dist[i][j] = w;
pq.push({w, i, j});
}
};
for (int i = 0; i < B; ++i) fill(dist[i], dist[i] + N, infI);
add(0, 0, S[0]);
while (!pq.empty()) {
auto[ww, i, j] = pq.top();
pq.pop();
if (used[i][j]) {
continue;
}
used[i][j] = true;
if (j == S[1]) {
cout << ww;
return 0;
}
for (auto t : adj[i][j]) {
add(t[0] + dist[i][j], t[1], t[2]);
}
if (i) {
add(dist[i][j], 0, j);
if (i + j < n) {
add(dist[i][j] + 1, i, i + j);
}
if (j - i > -1) {
add(dist[i][j] + 1, i, j - i);
}
}
}
cout << -1;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
82516 KB |
Output is correct |
2 |
Correct |
48 ms |
82412 KB |
Output is correct |
3 |
Correct |
48 ms |
82504 KB |
Output is correct |
4 |
Correct |
46 ms |
82520 KB |
Output is correct |
5 |
Correct |
49 ms |
82508 KB |
Output is correct |
6 |
Correct |
46 ms |
82508 KB |
Output is correct |
7 |
Correct |
46 ms |
82468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82528 KB |
Output is correct |
2 |
Correct |
47 ms |
82528 KB |
Output is correct |
3 |
Correct |
47 ms |
82512 KB |
Output is correct |
4 |
Correct |
46 ms |
82508 KB |
Output is correct |
5 |
Correct |
46 ms |
82484 KB |
Output is correct |
6 |
Correct |
46 ms |
82400 KB |
Output is correct |
7 |
Correct |
45 ms |
82416 KB |
Output is correct |
8 |
Correct |
45 ms |
82528 KB |
Output is correct |
9 |
Correct |
45 ms |
82556 KB |
Output is correct |
10 |
Correct |
47 ms |
82800 KB |
Output is correct |
11 |
Correct |
48 ms |
82656 KB |
Output is correct |
12 |
Correct |
48 ms |
82528 KB |
Output is correct |
13 |
Correct |
46 ms |
82528 KB |
Output is correct |
14 |
Correct |
48 ms |
82896 KB |
Output is correct |
15 |
Correct |
47 ms |
82888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82528 KB |
Output is correct |
2 |
Correct |
49 ms |
82424 KB |
Output is correct |
3 |
Correct |
46 ms |
82448 KB |
Output is correct |
4 |
Correct |
47 ms |
82472 KB |
Output is correct |
5 |
Correct |
48 ms |
82520 KB |
Output is correct |
6 |
Correct |
49 ms |
82524 KB |
Output is correct |
7 |
Correct |
45 ms |
82496 KB |
Output is correct |
8 |
Correct |
50 ms |
82428 KB |
Output is correct |
9 |
Correct |
46 ms |
82480 KB |
Output is correct |
10 |
Correct |
46 ms |
82792 KB |
Output is correct |
11 |
Correct |
46 ms |
82592 KB |
Output is correct |
12 |
Correct |
46 ms |
82616 KB |
Output is correct |
13 |
Correct |
45 ms |
82556 KB |
Output is correct |
14 |
Correct |
49 ms |
82892 KB |
Output is correct |
15 |
Correct |
51 ms |
82884 KB |
Output is correct |
16 |
Correct |
50 ms |
82528 KB |
Output is correct |
17 |
Correct |
47 ms |
83032 KB |
Output is correct |
18 |
Correct |
47 ms |
82516 KB |
Output is correct |
19 |
Correct |
50 ms |
82656 KB |
Output is correct |
20 |
Correct |
46 ms |
82588 KB |
Output is correct |
21 |
Correct |
47 ms |
82456 KB |
Output is correct |
22 |
Correct |
46 ms |
82524 KB |
Output is correct |
23 |
Correct |
49 ms |
82724 KB |
Output is correct |
24 |
Correct |
49 ms |
82856 KB |
Output is correct |
25 |
Correct |
47 ms |
82508 KB |
Output is correct |
26 |
Correct |
47 ms |
82584 KB |
Output is correct |
27 |
Correct |
46 ms |
82692 KB |
Output is correct |
28 |
Correct |
52 ms |
82892 KB |
Output is correct |
29 |
Correct |
54 ms |
82652 KB |
Output is correct |
30 |
Correct |
48 ms |
82496 KB |
Output is correct |
31 |
Correct |
52 ms |
82672 KB |
Output is correct |
32 |
Correct |
50 ms |
82640 KB |
Output is correct |
33 |
Correct |
61 ms |
83004 KB |
Output is correct |
34 |
Correct |
56 ms |
82944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82508 KB |
Output is correct |
2 |
Correct |
47 ms |
82472 KB |
Output is correct |
3 |
Correct |
47 ms |
82480 KB |
Output is correct |
4 |
Correct |
46 ms |
82448 KB |
Output is correct |
5 |
Correct |
47 ms |
82456 KB |
Output is correct |
6 |
Correct |
49 ms |
82456 KB |
Output is correct |
7 |
Correct |
47 ms |
82484 KB |
Output is correct |
8 |
Correct |
47 ms |
82492 KB |
Output is correct |
9 |
Correct |
50 ms |
82456 KB |
Output is correct |
10 |
Correct |
47 ms |
82764 KB |
Output is correct |
11 |
Correct |
46 ms |
82640 KB |
Output is correct |
12 |
Correct |
47 ms |
82604 KB |
Output is correct |
13 |
Correct |
47 ms |
82608 KB |
Output is correct |
14 |
Correct |
50 ms |
82868 KB |
Output is correct |
15 |
Correct |
48 ms |
82796 KB |
Output is correct |
16 |
Correct |
47 ms |
82548 KB |
Output is correct |
17 |
Correct |
49 ms |
83032 KB |
Output is correct |
18 |
Correct |
48 ms |
82584 KB |
Output is correct |
19 |
Correct |
47 ms |
82544 KB |
Output is correct |
20 |
Correct |
47 ms |
82508 KB |
Output is correct |
21 |
Correct |
47 ms |
82468 KB |
Output is correct |
22 |
Correct |
50 ms |
82460 KB |
Output is correct |
23 |
Correct |
48 ms |
82808 KB |
Output is correct |
24 |
Correct |
48 ms |
82968 KB |
Output is correct |
25 |
Correct |
47 ms |
82544 KB |
Output is correct |
26 |
Correct |
46 ms |
82620 KB |
Output is correct |
27 |
Correct |
47 ms |
82760 KB |
Output is correct |
28 |
Correct |
49 ms |
82956 KB |
Output is correct |
29 |
Correct |
53 ms |
82764 KB |
Output is correct |
30 |
Correct |
48 ms |
82616 KB |
Output is correct |
31 |
Correct |
51 ms |
82600 KB |
Output is correct |
32 |
Correct |
49 ms |
82588 KB |
Output is correct |
33 |
Correct |
62 ms |
82940 KB |
Output is correct |
34 |
Correct |
55 ms |
82828 KB |
Output is correct |
35 |
Correct |
52 ms |
84232 KB |
Output is correct |
36 |
Correct |
46 ms |
82788 KB |
Output is correct |
37 |
Correct |
56 ms |
84748 KB |
Output is correct |
38 |
Correct |
54 ms |
84764 KB |
Output is correct |
39 |
Correct |
53 ms |
84172 KB |
Output is correct |
40 |
Correct |
52 ms |
84212 KB |
Output is correct |
41 |
Correct |
54 ms |
84744 KB |
Output is correct |
42 |
Correct |
52 ms |
83400 KB |
Output is correct |
43 |
Correct |
54 ms |
83600 KB |
Output is correct |
44 |
Correct |
55 ms |
83404 KB |
Output is correct |
45 |
Correct |
84 ms |
87972 KB |
Output is correct |
46 |
Correct |
62 ms |
87996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
82508 KB |
Output is correct |
2 |
Correct |
46 ms |
82432 KB |
Output is correct |
3 |
Correct |
50 ms |
82508 KB |
Output is correct |
4 |
Correct |
48 ms |
82508 KB |
Output is correct |
5 |
Correct |
48 ms |
82508 KB |
Output is correct |
6 |
Correct |
49 ms |
82532 KB |
Output is correct |
7 |
Correct |
46 ms |
82484 KB |
Output is correct |
8 |
Correct |
47 ms |
82516 KB |
Output is correct |
9 |
Correct |
46 ms |
82468 KB |
Output is correct |
10 |
Correct |
46 ms |
82792 KB |
Output is correct |
11 |
Correct |
47 ms |
82636 KB |
Output is correct |
12 |
Correct |
47 ms |
82612 KB |
Output is correct |
13 |
Correct |
48 ms |
82488 KB |
Output is correct |
14 |
Correct |
48 ms |
82880 KB |
Output is correct |
15 |
Correct |
47 ms |
82916 KB |
Output is correct |
16 |
Correct |
46 ms |
82496 KB |
Output is correct |
17 |
Correct |
48 ms |
82988 KB |
Output is correct |
18 |
Correct |
49 ms |
82508 KB |
Output is correct |
19 |
Correct |
51 ms |
82444 KB |
Output is correct |
20 |
Correct |
46 ms |
82636 KB |
Output is correct |
21 |
Correct |
48 ms |
82548 KB |
Output is correct |
22 |
Correct |
46 ms |
82488 KB |
Output is correct |
23 |
Correct |
52 ms |
82740 KB |
Output is correct |
24 |
Correct |
47 ms |
82840 KB |
Output is correct |
25 |
Correct |
46 ms |
82608 KB |
Output is correct |
26 |
Correct |
47 ms |
82648 KB |
Output is correct |
27 |
Correct |
46 ms |
82700 KB |
Output is correct |
28 |
Correct |
49 ms |
82892 KB |
Output is correct |
29 |
Correct |
57 ms |
82700 KB |
Output is correct |
30 |
Correct |
49 ms |
82548 KB |
Output is correct |
31 |
Correct |
57 ms |
82568 KB |
Output is correct |
32 |
Correct |
48 ms |
82612 KB |
Output is correct |
33 |
Correct |
63 ms |
83036 KB |
Output is correct |
34 |
Correct |
58 ms |
82920 KB |
Output is correct |
35 |
Correct |
52 ms |
84224 KB |
Output is correct |
36 |
Correct |
47 ms |
82764 KB |
Output is correct |
37 |
Correct |
54 ms |
84800 KB |
Output is correct |
38 |
Correct |
58 ms |
84792 KB |
Output is correct |
39 |
Correct |
55 ms |
84164 KB |
Output is correct |
40 |
Correct |
52 ms |
84228 KB |
Output is correct |
41 |
Correct |
54 ms |
84632 KB |
Output is correct |
42 |
Correct |
52 ms |
83432 KB |
Output is correct |
43 |
Correct |
49 ms |
83596 KB |
Output is correct |
44 |
Correct |
48 ms |
83420 KB |
Output is correct |
45 |
Correct |
82 ms |
87948 KB |
Output is correct |
46 |
Correct |
60 ms |
87996 KB |
Output is correct |
47 |
Correct |
63 ms |
90344 KB |
Output is correct |
48 |
Correct |
58 ms |
84684 KB |
Output is correct |
49 |
Correct |
53 ms |
84384 KB |
Output is correct |
50 |
Correct |
52 ms |
83928 KB |
Output is correct |
51 |
Correct |
64 ms |
86260 KB |
Output is correct |
52 |
Correct |
64 ms |
86344 KB |
Output is correct |
53 |
Correct |
53 ms |
83212 KB |
Output is correct |
54 |
Correct |
46 ms |
82560 KB |
Output is correct |
55 |
Correct |
46 ms |
82592 KB |
Output is correct |
56 |
Correct |
54 ms |
83864 KB |
Output is correct |
57 |
Correct |
47 ms |
82700 KB |
Output is correct |
58 |
Correct |
56 ms |
83780 KB |
Output is correct |
59 |
Correct |
54 ms |
84036 KB |
Output is correct |
60 |
Correct |
58 ms |
84792 KB |
Output is correct |
61 |
Correct |
53 ms |
84080 KB |
Output is correct |
62 |
Correct |
69 ms |
88792 KB |
Output is correct |
63 |
Correct |
124 ms |
119080 KB |
Output is correct |
64 |
Correct |
127 ms |
132228 KB |
Output is correct |
65 |
Correct |
159 ms |
139884 KB |
Output is correct |
66 |
Correct |
596 ms |
145192 KB |
Output is correct |
67 |
Correct |
275 ms |
144788 KB |
Output is correct |