#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3+4;
const int K = 1e5+1;
const ll inf = 1e18;
struct node{
int a,b;
ll w;
};
bool operator<(node a,node b){
return a.w > b.w;
}
int n1,n,up_l,up_r;
int p[N],a[N*N];
priority_queue<node> d;
vector<int> b;
map<pair<int,int>,ll> dis;
void go(int u,int v,int x,int y,ll w){
if (min(u, v) < 0 || max(u, v) >= n) return;
if (a[u] != a[v]) return;
ll new_w = w + abs(a[u] - a[x]);
if (!dis.count({u, v}) || dis[{u, v}] > new_w)
d.push({u, v, dis[{u, v}] = new_w});
}
bool valid(int x,int y){
if (min(x, y) < 0 || max(x, y) >= n) return 0;
return a[x] == a[y] && (x != up_l || y != up_r);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (; n--; ){ cin >> p[n1++];
if (n1 >= 2 && p[n1-1] == p[n1-2]) n1--;
if (n1 >= 3 && p[n1-1] > p[n1-2] && p[n1-2] > p[n1-3])
p[n1-2] = p[n1-1], n1--;
if (n1 >= 3 && p[n1-1] < p[n1-2] && p[n1-2] < p[n1-3])
p[n1-2] = p[n1-1], n1--;
b.push_back(p[n1-1]);
}
// cout << "p[] = "; for (int i=0; i<n1; i++) cout << p[i] << " "; cout << "\n";
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
// cout << "b[] = "; for (int x : b) cout << x << " "; cout << "\n";
a[0] = 0, n = 1;
for (int i=1; i<n1; i++){
if (p[i-1] < p[i]) for (int x : b){
if (p[i-1] < x && x <= p[i]) a[n++] = x;
}
else for (int j=b.size()-1; j>=0; j--)
if (p[i-1] > b[j] && b[j] >= p[i]) a[n++] = b[j];
}
if (b.size() == n1){ ll ans = 0;
int l = 0,r = n-1; up_l = -1,up_r = -1;
for (; l != r; ){
if (valid(l+1, r-1)){ ans += abs(a[l+1] - a[l]);
up_l = l++, up_r = r--; continue;
}
if (valid(l-1, r-1)){ ans += abs(a[l-1] - a[l]);
up_l = l--, up_r = r--; continue;
}
if (valid(l+1, r+1)){ ans += abs(a[l+1] - a[l]);
up_l = l++, up_r = r++; continue;
}
if (valid(l-1, r+1)){ ans += abs(a[l-1] - a[l]);
up_l = l--, up_r = r++; continue;
}
}
cout << ans << "\n";
return 0;
}
// cout << "a[] = "; for (int i=0; i<n; i++) cout << a[i] << " "; cout << "\n";
d.push({0, n-1, dis[{0, n-1}] = 0});
for (; d.size(); ){ auto [x, y, w] = d.top(); d.pop();
if (x == y){ cout << w << "\n"; return 0;}
if (dis[{x, y}] != w) continue;
go(x+1, y+1, x, y, w), go(x-1, y+1, x, y, w);
go(x+1, y-1, x, y, w), go(x-1, y-1, x, y, w);
}
cout << "NO\n";
return 0;
}
Compilation message
climbers.cpp: In function 'int main()':
climbers.cpp:67:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
67 | if (b.size() == n1){ ll ans = 0;
| ~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Execution timed out |
1095 ms |
155516 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1072 ms |
155780 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1079 ms |
41036 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1604 KB |
Output is correct |
| 4 |
Correct |
5 ms |
892 KB |
Output is correct |
| 5 |
Correct |
46 ms |
4244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2448 KB |
Output is correct |
| 3 |
Execution timed out |
1064 ms |
66148 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1093 ms |
93504 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1064 ms |
106492 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1098 ms |
76116 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1091 ms |
93260 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1099 ms |
113996 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1099 ms |
96224 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1092 ms |
89896 KB |
Time limit exceeded |
