#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &x, T y){
x = min(x,y);
}
template<typename T>
void amax(T &x, T y){
x = max(x,y);
}
template<typename A,typename B>
string to_string(pair<A,B> p);
string to_string(const string &s){
return "'"+s+"'";
}
string to_string(const char* s){
return to_string((string)s);
}
string to_string(bool b){
return b?"true":"false";
}
template<typename A>
string to_string(A v){
string res = "{";
trav(x,v){
res += to_string(x)+",";
}
if(res.back() == ',') res.pop_back();
res += "}";
return res;
}
template<typename A,typename B>
string to_string(pair<A,B> p){
return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}
#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl
const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;
vector<array<ll,3>> adj[N][N];
bool vis[N][N];
void solve(int test_case){
ll n; cin >> n;
ll si,sj,ei,ej; cin >> si >> sj >> ei >> ej;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
vector<ll> b;
rep1(i,n) b.pb(a[i]+1);
b.pb(sj), b.pb(ej);
b.pb(1);
b.pb(-1);
sort(all(b));
b.resize(unique(all(b))-b.begin());
ll m = sz(b)-1;
vector<ll> ind(n+5);
// left/right
rep1(i,n){
// within row
ll pos = 1;
for(int j = 2; j <= m; ++j){
if(b[j] > a[i]+1) break;
pos = j;
ll w = b[j]-b[j-1];
adj[i][j-1].pb({i,j,w});
adj[i][j].pb({i,j-1,w});
}
ind[i] = pos;
// across row
if(i+1 <= n){
ll j = ind[i];
adj[i][j].pb({i+1,1,1});
adj[i+1][1].pb({i,j,1});
}
}
// up/down
rep1(i,n){
rep1(j,ind[i]){
// go up
if(i-1 >= 1){
ll j2 = min((ll)j,ind[i-1]);
adj[i][j].pb({i-1,j2,1});
}
// go down
if(i+1 <= n){
ll j2 = min((ll)j,ind[i+1]);
adj[i][j].pb({i+1,j2,1});
}
}
}
sj = lower_bound(all(b),sj)-b.begin();
ej = lower_bound(all(b),ej)-b.begin();
priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
auto ins = [&](ll i, ll j, ll cost){
pq.push({cost,i,j});
};
ins(si,sj,0);
while(!pq.empty()){
auto [cost,i,j] = pq.top();
pq.pop();
if(vis[i][j]) conts;
vis[i][j] = 1;
if(i == ei and j == ej){
cout << cost << endl;
return;
}
for(auto [i2,j2,w] : adj[i][j]){
ins(i2,j2,cost+w);
}
}
assert(0);
}
int main(){
fastio;
int t = 1;
// cin >> t;
rep1(i,t){
solve(i);
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
24152 KB |
Output is correct |
2 |
Correct |
10 ms |
24152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
24152 KB |
Output is correct |
2 |
Correct |
9 ms |
24156 KB |
Output is correct |
3 |
Correct |
10 ms |
23984 KB |
Output is correct |
4 |
Correct |
11 ms |
24076 KB |
Output is correct |
5 |
Correct |
11 ms |
24156 KB |
Output is correct |
6 |
Correct |
9 ms |
24136 KB |
Output is correct |
7 |
Correct |
10 ms |
24156 KB |
Output is correct |
8 |
Correct |
13 ms |
24156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
24152 KB |
Output is correct |
2 |
Correct |
10 ms |
24152 KB |
Output is correct |
3 |
Correct |
10 ms |
24152 KB |
Output is correct |
4 |
Correct |
15 ms |
24924 KB |
Output is correct |
5 |
Correct |
12 ms |
24952 KB |
Output is correct |
6 |
Correct |
11 ms |
24668 KB |
Output is correct |
7 |
Correct |
12 ms |
25432 KB |
Output is correct |
8 |
Correct |
12 ms |
25388 KB |
Output is correct |
9 |
Correct |
199 ms |
50300 KB |
Output is correct |
10 |
Correct |
214 ms |
51140 KB |
Output is correct |
11 |
Correct |
201 ms |
50984 KB |
Output is correct |
12 |
Correct |
322 ms |
69652 KB |
Output is correct |
13 |
Correct |
373 ms |
70728 KB |
Output is correct |
14 |
Correct |
115 ms |
71680 KB |
Output is correct |
15 |
Correct |
88 ms |
75092 KB |
Output is correct |
16 |
Correct |
104 ms |
74520 KB |
Output is correct |
17 |
Correct |
283 ms |
75128 KB |
Output is correct |
18 |
Correct |
328 ms |
78904 KB |
Output is correct |
19 |
Correct |
341 ms |
78976 KB |
Output is correct |
20 |
Correct |
68 ms |
33104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
24152 KB |
Output is correct |
2 |
Correct |
10 ms |
24152 KB |
Output is correct |
3 |
Correct |
10 ms |
24152 KB |
Output is correct |
4 |
Correct |
9 ms |
24156 KB |
Output is correct |
5 |
Correct |
10 ms |
23984 KB |
Output is correct |
6 |
Correct |
11 ms |
24076 KB |
Output is correct |
7 |
Correct |
11 ms |
24156 KB |
Output is correct |
8 |
Correct |
9 ms |
24136 KB |
Output is correct |
9 |
Correct |
10 ms |
24156 KB |
Output is correct |
10 |
Correct |
13 ms |
24156 KB |
Output is correct |
11 |
Correct |
15 ms |
24924 KB |
Output is correct |
12 |
Correct |
12 ms |
24952 KB |
Output is correct |
13 |
Correct |
11 ms |
24668 KB |
Output is correct |
14 |
Correct |
12 ms |
25432 KB |
Output is correct |
15 |
Correct |
12 ms |
25388 KB |
Output is correct |
16 |
Correct |
199 ms |
50300 KB |
Output is correct |
17 |
Correct |
214 ms |
51140 KB |
Output is correct |
18 |
Correct |
201 ms |
50984 KB |
Output is correct |
19 |
Correct |
322 ms |
69652 KB |
Output is correct |
20 |
Correct |
373 ms |
70728 KB |
Output is correct |
21 |
Correct |
115 ms |
71680 KB |
Output is correct |
22 |
Correct |
88 ms |
75092 KB |
Output is correct |
23 |
Correct |
104 ms |
74520 KB |
Output is correct |
24 |
Correct |
283 ms |
75128 KB |
Output is correct |
25 |
Correct |
328 ms |
78904 KB |
Output is correct |
26 |
Correct |
341 ms |
78976 KB |
Output is correct |
27 |
Correct |
68 ms |
33104 KB |
Output is correct |
28 |
Correct |
13 ms |
25432 KB |
Output is correct |
29 |
Correct |
12 ms |
25692 KB |
Output is correct |
30 |
Correct |
12 ms |
25384 KB |
Output is correct |
31 |
Correct |
13 ms |
25436 KB |
Output is correct |
32 |
Correct |
13 ms |
25476 KB |
Output is correct |
33 |
Correct |
239 ms |
59772 KB |
Output is correct |
34 |
Correct |
266 ms |
64088 KB |
Output is correct |
35 |
Correct |
286 ms |
65296 KB |
Output is correct |
36 |
Correct |
335 ms |
81108 KB |
Output is correct |
37 |
Correct |
110 ms |
81112 KB |
Output is correct |
38 |
Correct |
101 ms |
80896 KB |
Output is correct |
39 |
Correct |
277 ms |
80888 KB |
Output is correct |
40 |
Correct |
155 ms |
80888 KB |
Output is correct |
41 |
Correct |
180 ms |
80888 KB |
Output is correct |
42 |
Correct |
299 ms |
104872 KB |
Output is correct |
43 |
Correct |
308 ms |
104620 KB |
Output is correct |
44 |
Correct |
68 ms |
34628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
24152 KB |
Output is correct |
2 |
Correct |
9 ms |
24156 KB |
Output is correct |
3 |
Correct |
10 ms |
23984 KB |
Output is correct |
4 |
Correct |
11 ms |
24076 KB |
Output is correct |
5 |
Correct |
11 ms |
24156 KB |
Output is correct |
6 |
Correct |
9 ms |
24136 KB |
Output is correct |
7 |
Correct |
10 ms |
24156 KB |
Output is correct |
8 |
Correct |
13 ms |
24156 KB |
Output is correct |
9 |
Correct |
15 ms |
24924 KB |
Output is correct |
10 |
Correct |
12 ms |
24952 KB |
Output is correct |
11 |
Correct |
11 ms |
24668 KB |
Output is correct |
12 |
Correct |
12 ms |
25432 KB |
Output is correct |
13 |
Correct |
12 ms |
25388 KB |
Output is correct |
14 |
Correct |
13 ms |
25432 KB |
Output is correct |
15 |
Correct |
12 ms |
25692 KB |
Output is correct |
16 |
Correct |
12 ms |
25384 KB |
Output is correct |
17 |
Correct |
13 ms |
25436 KB |
Output is correct |
18 |
Correct |
13 ms |
25476 KB |
Output is correct |
19 |
Runtime error |
130 ms |
99500 KB |
Execution killed with signal 11 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
24152 KB |
Output is correct |
2 |
Correct |
10 ms |
24152 KB |
Output is correct |
3 |
Correct |
10 ms |
24152 KB |
Output is correct |
4 |
Correct |
9 ms |
24156 KB |
Output is correct |
5 |
Correct |
10 ms |
23984 KB |
Output is correct |
6 |
Correct |
11 ms |
24076 KB |
Output is correct |
7 |
Correct |
11 ms |
24156 KB |
Output is correct |
8 |
Correct |
9 ms |
24136 KB |
Output is correct |
9 |
Correct |
10 ms |
24156 KB |
Output is correct |
10 |
Correct |
13 ms |
24156 KB |
Output is correct |
11 |
Correct |
15 ms |
24924 KB |
Output is correct |
12 |
Correct |
12 ms |
24952 KB |
Output is correct |
13 |
Correct |
11 ms |
24668 KB |
Output is correct |
14 |
Correct |
12 ms |
25432 KB |
Output is correct |
15 |
Correct |
12 ms |
25388 KB |
Output is correct |
16 |
Correct |
199 ms |
50300 KB |
Output is correct |
17 |
Correct |
214 ms |
51140 KB |
Output is correct |
18 |
Correct |
201 ms |
50984 KB |
Output is correct |
19 |
Correct |
322 ms |
69652 KB |
Output is correct |
20 |
Correct |
373 ms |
70728 KB |
Output is correct |
21 |
Correct |
115 ms |
71680 KB |
Output is correct |
22 |
Correct |
88 ms |
75092 KB |
Output is correct |
23 |
Correct |
104 ms |
74520 KB |
Output is correct |
24 |
Correct |
283 ms |
75128 KB |
Output is correct |
25 |
Correct |
328 ms |
78904 KB |
Output is correct |
26 |
Correct |
341 ms |
78976 KB |
Output is correct |
27 |
Correct |
68 ms |
33104 KB |
Output is correct |
28 |
Correct |
13 ms |
25432 KB |
Output is correct |
29 |
Correct |
12 ms |
25692 KB |
Output is correct |
30 |
Correct |
12 ms |
25384 KB |
Output is correct |
31 |
Correct |
13 ms |
25436 KB |
Output is correct |
32 |
Correct |
13 ms |
25476 KB |
Output is correct |
33 |
Correct |
239 ms |
59772 KB |
Output is correct |
34 |
Correct |
266 ms |
64088 KB |
Output is correct |
35 |
Correct |
286 ms |
65296 KB |
Output is correct |
36 |
Correct |
335 ms |
81108 KB |
Output is correct |
37 |
Correct |
110 ms |
81112 KB |
Output is correct |
38 |
Correct |
101 ms |
80896 KB |
Output is correct |
39 |
Correct |
277 ms |
80888 KB |
Output is correct |
40 |
Correct |
155 ms |
80888 KB |
Output is correct |
41 |
Correct |
180 ms |
80888 KB |
Output is correct |
42 |
Correct |
299 ms |
104872 KB |
Output is correct |
43 |
Correct |
308 ms |
104620 KB |
Output is correct |
44 |
Correct |
68 ms |
34628 KB |
Output is correct |
45 |
Runtime error |
130 ms |
99500 KB |
Execution killed with signal 11 |
46 |
Halted |
0 ms |
0 KB |
- |