#include <bits/stdc++.h>
using namespace std;
const int oo = INT_MAX;
const int nmax = 5e3;
int n;
int v[nmax + 5];
int d[nmax + 5][nmax + 5][2];
bool sel[nmax + 5][nmax + 5][2];
typedef pair<pair<int,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 |
6748 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15196 KB |
Output is correct |
| 3 |
Correct |
7 ms |
43768 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
129792 KB |
Output isn't correct |
| 5 |
Incorrect |
58 ms |
216916 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
19292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
7000 KB |
Output is correct |
| 2 |
Correct |
2 ms |
15452 KB |
Output is correct |
| 3 |
Correct |
72 ms |
43764 KB |
Output is correct |
| 4 |
Incorrect |
129 ms |
128272 KB |
Output isn't correct |
| 5 |
Incorrect |
162 ms |
131408 KB |
Output isn't correct |
| 6 |
Incorrect |
165 ms |
170916 KB |
Output isn't correct |
| 7 |
Incorrect |
175 ms |
171100 KB |
Output isn't correct |
| 8 |
Incorrect |
152 ms |
216148 KB |
Output isn't correct |
| 9 |
Incorrect |
215 ms |
215052 KB |
Output isn't correct |
| 10 |
Incorrect |
221 ms |
216076 KB |
Output isn't correct |
