#include <bits/stdc++.h>
using namespace std;
const long long oo = LLONG_MAX;
const int nmax = 5e3;
int n;
int v[nmax + 5];
long long d[nmax + 5][nmax + 5][2];
bool sel[nmax + 5][nmax + 5][2];
typedef pair<pair<long long,int>,pair<int,int>> pii;
priority_queue<pii,vector<pii>,greater<pii>> h;
bool inclus(int a, int x, int y)
{
if(x > y)
{
swap(x, y);
}
return (x <= a && a <= y);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
d[i][j][0] = d[i][j][1] = oo;
}
}
d[1][n][0] = d[1][n - 1][1] = 0;
h.push({{0,0},{1,n}});
h.push({{0,1},{1,n-1}});
while(!h.empty())
{
while(!h.empty() && sel[h.top().second.first][h.top().second.second][h.top().first.second])
{
h.pop();
}
if(h.empty())
{
break;
}
int tip = h.top().first.second;
int st = h.top().second.first;
int dr = h.top().second.second;
if(tip==0 && st==dr-1)
{
cout<<h.top().first.first<<'\n';
return 0;
}
if(tip==1 && st==dr)
{
cout<<h.top().first.first<<'\n';
return 0;
}
h.pop();
sel[st][dr][tip] = true;
if(tip==0)
{
/// st e intre pozitii
/// st se duce la stanga, dr se duce la stanga
if(dr!=1 && inclus(v[st], v[dr - 1], v[dr]))
{
if(d[st][dr][0] + abs(v[st] - v[dr]) < d[st][dr - 1][1])
{
d[st][dr - 1][1] = d[st][dr][0] + abs(v[st] - v[dr]);
h.push({{d[st][dr - 1][1],1},{st, dr - 1}});
}
}
/// st se duce la stanga, dr se duce la dreapta
if(dr!=n && inclus(v[st], v[dr], v[dr + 1]))
{
if(d[st][dr][0] + abs(v[st] - v[dr]) < d[st][dr][1])
{
d[st][dr][1] = d[st][dr][0] + abs(v[st] - v[dr]);
h.push({{d[st][dr][1],1},{st,dr}});
}
}
/// st se duce la dreapta, dr se duce la stanga
if(dr!=1 && inclus(v[st + 1], v[dr - 1], v[dr]))
{
if(d[st][dr][0] + abs(v[st + 1] - v[dr]) < d[st + 1][dr - 1][1])
{
d[st + 1][dr - 1][1] = d[st][dr][0] + abs(v[st + 1] - v[dr]);
h.push({{d[st + 1][dr - 1][1], 1},{st + 1, dr - 1}});
}
}
/// st se duce la dreapta, dr se duce la dreapta
if(dr!=n && inclus(v[st + 1], v[dr], v[dr + 1]))
{
if(d[st][dr][0] + abs(v[st + 1] - v[dr]) < d[st + 1][dr][1])
{
d[st + 1][dr][1] = d[st][dr][0] + abs(v[st + 1] - v[dr]);
h.push({{d[st + 1][dr][1], 1},{st + 1, dr}});
}
}
/// dr se duce la stanga
if(dr!=1 && inclus(v[dr - 1], v[st], v[st + 1]))
{
if(d[st][dr][0] + abs(v[dr - 1] - v[dr]) < d[st][dr - 1][0])
{
d[st][dr - 1][0] = d[st][dr][0] + abs(v[dr - 1] - v[dr]);
h.push({{d[st][dr - 1][0], 0},{st,dr-1}});
}
}
/// dr se duce la dreapta
if(dr!=n && inclus(v[dr + 1], v[st], v[st + 1]))
{
if(d[st][dr][0] + abs(v[dr + 1] - v[dr]) < d[st][dr + 1][0])
{
d[st][dr + 1][0] = d[st][dr][0] + abs(v[dr + 1] - v[dr]);
h.push({{d[st][dr + 1][0], 0},{st, dr + 1}});
}
}
}
else
{
/// dr e intre pozitii
/// dr se duce la stanga, st se duce la stanga
if(st!=1 && inclus(v[dr], v[st], v[st - 1]))
{
if(d[st][dr][1] + abs(v[dr] - v[st]) < d[st - 1][dr][0])
{
d[st - 1][dr][0] = d[st][dr][1] + abs(v[dr] - v[st]);
h.push({{d[st - 1][dr][0], 0},{st - 1, dr}});
}
}
/// dr se duce la stanga, st se duce la dreapta
if(st!=n && inclus(v[dr], v[st], v[st + 1]))
{
if(d[st][dr][1] + abs(v[dr] - v[st]) < d[st][dr][0])
{
d[st][dr][0] = d[st][dr][1] + abs(v[dr] - v[st]);
h.push({{d[st][dr][0],0},{st,dr}});
}
}
/// dr se duce la dreapta, st se duce la stanga
if(st!=1 && inclus(v[dr + 1], v[st],v[st - 1]))
{
if(d[st][dr][1] + abs(v[dr + 1] - v[st]) < d[st - 1][dr + 1][0])
{
d[st - 1][dr + 1][0] = d[st][dr][1] + abs(v[dr + 1] - v[st]);
h.push({{d[st - 1][dr + 1][0], 0},{st - 1, dr + 1}});
}
}
/// dr se duce la dreapta, st se duce la dreapta
if(st!=n && inclus(v[dr + 1], v[st], v[st + 1]))
{
if(d[st][dr][1] + abs(v[dr + 1] - v[st]) < d[st][dr + 1][0])
{
d[st][dr + 1][0] = d[st][dr][1] + abs(v[dr + 1] - v[st]);
h.push({{d[st][dr + 1][0], 0},{st, dr + 1}});
}
}
/// st se duce la stanga
if(st!=1 && inclus(v[st - 1], v[dr], v[dr + 1]))
{
if(d[st][dr][1] + abs(v[st - 1] - v[st]) < d[st - 1][dr][1])
{
d[st - 1][dr][1] = d[st][dr][1] + abs(v[st - 1] - v[st]);
h.push({{d[st - 1][dr][1], 1},{st - 1, dr}});
}
}
/// st se duce la dreapta
if(st!=n && inclus(v[st + 1], v[dr], v[dr + 1]))
{
if(d[st][dr][1] + abs(v[st + 1] - v[st]) < d[st + 1][dr][1])
{
d[st + 1][dr][1] = d[st][dr][1] + abs(v[st + 1] - v[st]);
h.push({{d[st + 1][dr][1], 1},{st + 1, dr}});
}
}
}
}
cout<<"NO"<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27740 KB |
Output is correct |
| 3 |
Correct |
10 ms |
82740 KB |
Output is correct |
| 4 |
Correct |
37 ms |
246576 KB |
Output is correct |
| 5 |
Correct |
91 ms |
413008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10976 KB |
Output is correct |
| 5 |
Correct |
4 ms |
35676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27740 KB |
Output is correct |
| 3 |
Correct |
80 ms |
82768 KB |
Output is correct |
| 4 |
Correct |
144 ms |
245204 KB |
Output is correct |
| 5 |
Correct |
185 ms |
248272 KB |
Output is correct |
| 6 |
Correct |
178 ms |
327000 KB |
Output is correct |
| 7 |
Correct |
200 ms |
326992 KB |
Output is correct |
| 8 |
Correct |
179 ms |
412024 KB |
Output is correct |
| 9 |
Correct |
208 ms |
410900 KB |
Output is correct |
| 10 |
Correct |
236 ms |
412020 KB |
Output is correct |
