#include<bits/stdc++.h>
using namespace std;
typedef int ll; // ! CAREFUL
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef pair<int, int> pi;
typedef vector<bool> vb;
#define fi first
#define se second
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false)
#define pb push_back
ll solve(ll n, ll sl, ll sc, ll el, ll ec, const vll& l) {
vll prefl(n + 1, 0);
for(ll i = 0; i < n; i++) {
prefl[i + 1] = prefl[i] + l[i];
}
ll totn = prefl[n];
set<ll> vis;
typedef pair<ll, pll> ppll;
typedef vector<ppll> vppll;
// priority_queue<ppll, vppll, greater<ppll>> pq;
queue<ppll> pq;
ll s = prefl[sl] + sc, e = prefl[el] + ec;
ll ans = 0;
pq.push({0, {sl, sc}});
while(!pq.empty()) {
auto [cdist, curi] = pq.front();
pq.pop();
auto [li, ci] = curi;
ll i = prefl[li] + ci;
if(vis.count(i) > 0) continue;
vis.insert(i);
if(i == e) {
ans = cdist;
break;
}
// can move up
if(li > 0) {
pq.push({cdist + 1, {li - 1, min(ci, l[li - 1] - 1)}});
}
// can move down
if(li < n - 1) {
pq.push({cdist + 1, {li + 1, min(ci, l[li + 1] - 1)}});
}
// can move left
if(i > 0) {
if(ci > 0) {
pq.push({cdist + 1, {li, ci - 1}});
} else {
pq.push({cdist + 1, {li - 1, l[li - 1] - 1}});
}
}
// can move right
if(i < totn - 1) {
if(ci < l[li] - 1) {
pq.push({cdist + 1, {li, ci + 1}});
} else {
pq.push({cdist + 1, {li + 1, 0}});
}
}
}
return ans;
}
int main() {
IOS;
ll n;
cin >> n;
ll sl, sc;
ll el, ec;
cin >> sl >> sc;
cin >> el >> ec;
sl--; sc--;
el--; ec--;
vll l(n, 0);
for(ll& lv : l) {
cin >> lv;
lv++; // ! WARNING, already added one
}
cout << solve(n, sl, sc, el, ec, l) << endl;
return 0;
}
Compilation message
Main.cpp: In function 'll solve(ll, ll, ll, ll, ll, const vll&)':
Main.cpp:34:8: warning: unused variable 's' [-Wunused-variable]
34 | ll s = prefl[sl] + sc, e = prefl[el] + ec;
| ^
Main.cpp:29:26: warning: typedef 'vppll' locally defined but not used [-Wunused-local-typedefs]
29 | typedef vector<ppll> vppll;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
4094 ms |
323624 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
38 ms |
4428 KB |
Output is correct |
5 |
Correct |
68 ms |
7252 KB |
Output is correct |
6 |
Correct |
8 ms |
1372 KB |
Output is correct |
7 |
Correct |
177 ms |
16732 KB |
Output is correct |
8 |
Correct |
3797 ms |
234860 KB |
Output is correct |
9 |
Correct |
2258 ms |
116388 KB |
Output is correct |
10 |
Correct |
1925 ms |
105552 KB |
Output is correct |
11 |
Correct |
2424 ms |
127056 KB |
Output is correct |
12 |
Correct |
1424 ms |
89128 KB |
Output is correct |
13 |
Correct |
2827 ms |
158620 KB |
Output is correct |
14 |
Correct |
602 ms |
49160 KB |
Output is correct |
15 |
Correct |
64 ms |
6744 KB |
Output is correct |
16 |
Correct |
92 ms |
9500 KB |
Output is correct |
17 |
Correct |
950 ms |
71124 KB |
Output is correct |
18 |
Correct |
1360 ms |
82260 KB |
Output is correct |
19 |
Correct |
1121 ms |
117840 KB |
Output is correct |
20 |
Correct |
1222 ms |
73852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Execution timed out |
4094 ms |
323624 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
4094 ms |
323624 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Execution timed out |
4094 ms |
323624 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |