#include <bits/stdc++.h>
using namespace std;
#define F0R(i,a) for(int i=0;i<(a);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORd(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0Rd(i,a) for(int i=(a)-1;i>=0;--i)
typedef vector<int> vi;
void solve(){
int n;
cin>>n;
int si,sj,ei,ej;
cin>>si>>sj>>ei>>ej;
si--,sj--,ei--,ej--;
vi a(n);
F0R(i,n)cin>>a[i];
int res=2e9;
{
int aux=0,mn=sj;
FOR(i,min(si,ei),max(si,ei)+1){
mn=min(mn,a[i]);
}
res=min(res,abs(si-ei)+abs(mn-ej));
}
vi mn(n, 1e9);
int tmp=sj;
FOR(i,si,n){
if(i>si)
mn[i]=min({mn[i],mn[i-1]+1,i-si+a[i-1]-tmp});
tmp=min(tmp,a[i]);
mn[i]=min(mn[i],i-si+tmp);
}
tmp=sj;
FORd(i,0,si){
tmp=min(tmp,a[i]);
if(i+1<n){
mn[i+1]=min(mn[i+1],a[i]-tmp+si-i);
mn[i]=min(mn[i],mn[i+1]+1);
}
}
//F0R(i,n)cout<<mn[i]<<" ";
//cout<<endl;
tmp=1e9;
F0R(i,n){
mn[i]=min(mn[i],tmp);
tmp=min(tmp,mn[i]);
tmp++;
}
tmp=1e9;
F0Rd(i,n){
mn[i]=min(mn[i],tmp);
tmp=min(tmp,mn[i]);
tmp++;
}
//F0R(i,n)cout<<mn[i]<<" ";cout<<endl;
res=min(res,mn[ei]+ej);
tmp=1e9;
FOR(i,ei,n-1){
tmp=min(tmp,a[i]);
res=min(res,mn[i+1]+abs(ej-tmp)+i-ei+1);
//cout<<i<<" "<<mn[i+1]<<" "<<ej-tmp<<" "<<i-ei<<" "<<endl;
}
//cout<<res<<endl;
tmp=a[ei];
FORd(i,1,ei+1){
tmp=min(tmp,a[i-1]);
res=min(res,mn[i]+abs(ej-tmp)+ei-i+2);
}
cout<<res<<endl;
}
int main() {
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:20:13: warning: unused variable 'aux' [-Wunused-variable]
20 | int aux=0,mn=sj;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
436 KB |
Output is correct |
3 |
Correct |
1 ms |
440 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
440 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
436 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
352 KB |
Output is correct |
9 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
436 KB |
Output is correct |
5 |
Correct |
1 ms |
440 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
440 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
436 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
352 KB |
Output is correct |
16 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
436 KB |
Output is correct |
3 |
Correct |
1 ms |
440 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
440 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
436 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
352 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
276 ms |
15884 KB |
Output is correct |
20 |
Correct |
251 ms |
16064 KB |
Output is correct |
21 |
Correct |
289 ms |
16556 KB |
Output is correct |
22 |
Correct |
212 ms |
15276 KB |
Output is correct |
23 |
Correct |
306 ms |
18796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
436 KB |
Output is correct |
5 |
Correct |
1 ms |
440 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
440 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
436 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
352 KB |
Output is correct |
16 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |