#include <bits/stdc++.h>
using namespace std;
const int MAX_STARI = 6300000;
const long long INF = 1e18;
vector<pair<pair<int,int>,pair<int,int>>> edges;
vector<pair<int,int>> con[MAX_STARI];
long long dist[MAX_STARI];
void add_edge(int v1, int m1, int v2, int m2)
{
edges.push_back({{v1,m1},{v2,m2}});
}
priority_queue<pair<long long,int>> pq;
map<pair<int,int>,int> mp,nrm;
//v - varf, m - muchie
int n,p[5005],cate;
void normalizare()
{
for(auto [x,y]:edges)
{
mp[x]++;
mp[y]++;
}
for(auto it:mp)
if(it.second)
{
nrm[it.first]=++cate;
//cerr<<it.first.first<<" "<<it.first.second<<" zzz\n";
}
}
void afis(int v, int m)
{
cerr<<"in varful "<<v<<" si pe dreapta "<<m<<" avem "<<dist[nrm[{v,m}]]<<"\n";
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>p[i];
assert(p[1]==0);
assert(p[n]==0);
for(int v=1;v<=n;v++)
{
for(int m=1;m<n;m++)
{
if(p[v] < min(p[m],p[m+1]) || p[v] > max(p[m],p[m+1]))
continue;
for(int newv:{v-1,v+1})
{
if(newv>=1 && newv<=n && min(p[m],p[m+1]) <= p[newv] && p[newv] <= max(p[m],p[m+1]))
{
add_edge(v,m,newv,m);
}
}
if(p[v] == p[m] && m-1>0)
{
add_edge(v,m,v,m-1);
}
if(p[v] == p[m+1] && m+1<n)
{
add_edge(v,m,v,m+1);
}
if(p[v] == p[m])
{
if(v<n) add_edge(v,m,m,v);
if(v>1) add_edge(v,m,m,v-1);
}
if(p[v] == p[m+1])
{
if(v<n) add_edge(v,m,m+1,v);
if(v>1) add_edge(v,m,m+1,v-1);
}
if(v+1<n && min(p[v],p[v+1]) <= p[m] && p[m] <= max(p[v],p[v+1]))
{
add_edge(v,m,m,v);
}
if(v-1>0 && min(p[v],p[v-1]) <= p[m] && p[m] <= max(p[v],p[v-1]))
{
add_edge(v,m,m,v-1);
}
if(v+1<n && min(p[v],p[v+1]) <= p[m+1] && p[m+1] <= max(p[v],p[v+1]))
{
add_edge(v,m,m+1,v);
}
if(v-1>0 && min(p[v],p[v-1]) <= p[m+1] && p[m+1] <= max(p[v],p[v-1]))
{
add_edge(v,m,m+1,v-1);
}
}
}
mp[{n,1}]++;
mp[{1,n-1}]++;
normalizare();
for(auto [x,y]:edges)
{
int a = nrm[x], b = nrm[y];
con[a].push_back({b,abs(p[x.first]-p[y.first])});
con[b].push_back({a,abs(p[x.first]-p[y.first])});
}
for(int i=1;i<=cate;i++)
dist[i]=INF;
dist[nrm[{n,1}]]=0;
dist[nrm[{1,n-1}]]=0;
pq.push({0,nrm[{n,1}]});
pq.push({0,nrm[{1,n-1}]});
while(!pq.empty())
{
long long cdist = -pq.top().first;
int nod = pq.top().second;
pq.pop();
if(dist[nod]!=cdist)
continue;
//cerr<<nod<<" new dist "<<dist[nod]<<"\n";
for(auto [adj,c]:con[nod])
{
if(cdist + c < dist[adj])
{
dist[adj] = cdist + c;
pq.push({-dist[adj],adj});
}
}
}
long long rez=INF;
for(int m=1;m<n;m++)
{
rez = min(rez, dist[nrm[{m,m}]]);
rez = min(rez, dist[nrm[{m+1,m}]]);
}
/*for(int v=1;v<=n;v++)
for(int m=1;m<n;m++)
{
if(p[v] < min(p[m],p[m+1]) || p[v] > max(p[m],p[m+1]))
continue;
afis(v,m);
}*/
assert(rez<INF);
cout<<rez;
return 0;
}
/*
7
0 10 1 20 5 10 0
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
70 ms |
151076 KB |
Output is correct |
| 2 |
Correct |
105 ms |
158148 KB |
Output is correct |
| 3 |
Correct |
738 ms |
239856 KB |
Output is correct |
| 4 |
Execution timed out |
1071 ms |
397600 KB |
Time limit exceeded |
| 5 |
Runtime error |
459 ms |
524288 KB |
Execution killed with signal 9 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
63 ms |
150352 KB |
Output is correct |
| 2 |
Correct |
64 ms |
150608 KB |
Output is correct |
| 3 |
Correct |
78 ms |
153288 KB |
Output is correct |
| 4 |
Correct |
64 ms |
151756 KB |
Output is correct |
| 5 |
Correct |
153 ms |
164280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
76 ms |
153800 KB |
Output is correct |
| 2 |
Correct |
212 ms |
174584 KB |
Output is correct |
| 3 |
Execution timed out |
1057 ms |
319152 KB |
Time limit exceeded |
| 4 |
Runtime error |
429 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
413 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
419 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
418 ms |
524288 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
448 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
476 ms |
524288 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
430 ms |
524288 KB |
Execution killed with signal 9 |
