#include <bits/stdc++.h>
using namespace std;
int n;
vector <pair <int , int> > v[10000000];
int dp[10000000] , vinit[5010];
priority_queue <pair <int , int> > h;
int cod[25000000] , decod[25000000];
int encode (int x , int y){
x--;
y--;
return cod[x * n + y];
}
pair <int , int> decode (int cod){
cod = decod[cod];
return make_pair(cod / n + 1 , cod % n + 1);
}
void muchie (int x1 , int y1 , int x2 , int y2 , int cost){
v[encode(x1 , y1)].push_back(make_pair(encode(x2 , y2) , cost));
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int i , ers , cost , nod , val , vecin , j , elem;
pair <int , int> actual;
fscanf (fin,"%d",&n);
for (i = 1 ; i <= n ; i++)
fscanf (fin,"%d",&vinit[i]);
ers = 0;
for (i = 2 ; i < n ; i++){
if ((vinit[i - 1] <= vinit[i] && vinit[i] <= vinit[i + 1]) || (vinit[i - 1] >= vinit[i] && vinit[i] >= vinit[i + 1]))
ers++; /// il stergi pe vinit[i]
else vinit[i - ers] = vinit[i];
}
vinit[n - ers] = vinit[n];
n -= ers;
elem = 0;
/// acum vinit ul e "condensat"
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j <= n ; j++){
if ((vinit[j] <= vinit[i] && vinit[i] <= vinit[j + 1]) || (vinit[j] >= vinit[i] && vinit[i] >= vinit[j + 1])){
val = (i - 1) * n + j - 1;
cod[val] = ++elem;
decod[elem] = val;
}
}
}
for (i = 1 ; i <= n ; i++){
for (j = 1 ; j < n ; j++){
//if (i == 3 && j == 4)
//printf ("a");
/// daca cu un om sunt pe nodul i si cu celalalt pe segmentul j , j + 1
if ((vinit[j] <= vinit[i] && vinit[i] <= vinit[j + 1]) || (vinit[j] >= vinit[i] && vinit[i] >= vinit[j + 1])){
/// e o stare vinitalida
if (vinit[j] < vinit[j + 1]){ /// segm e crescator
if (i != n){ /// ma duc in nodul i + 1, deci nu parasesc segm
if (vinit[i + 1] > vinit[i] && vinit[i + 1] <= vinit[j + 1]){
muchie (i , j , i + 1 , j , vinit[i + 1] - vinit[i]); /// se pastreaza segmentul
}
else if (vinit[i + 1] < vinit[i] && vinit[i + 1] >= vinit[j]){
muchie (i , j , i + 1 , j , vinit[i] - vinit[i + 1]);
}
}
if (i != 1){ /// ma duc in nodul i - 1, raman pe acelasi segm
if (vinit[i - 1] > vinit[i] && vinit[i - 1] <= vinit[j + 1]){
muchie (i , j , i - 1 , j , vinit[i - 1] - vinit[i]); /// se pastreaza segmentul
}
else if (vinit[i - 1] < vinit[i] && vinit[i - 1] >= vinit[j]){
muchie (i , j , i - 1 , j , vinit[i] - vinit[i - 1]);
}
}
/// --------------------------------------------------
/// sunt intre j si j + 1
/// vinitreau sa ma mut in j, adc cobor
if (i != n && vinit[i] > vinit[i + 1] && vinit[i] - vinit[i + 1] >= vinit[i] - vinit[j]){
muchie (i , j , j , i , vinit[i] - vinit[j]);
}
if (i != 1 && vinit[i] > vinit[i - 1] && vinit[i] - vinit[i - 1] >= vinit[i] - vinit[j]){
muchie (i , j , j , i - 1 , vinit[i] - vinit[j]);
}
/// in j + 1 , adc urc
if (i != n && vinit[i] < vinit[i + 1] && vinit[i + 1] - vinit[i] >= vinit[j + 1] - vinit[i]){
muchie (i , j , j + 1 , i , vinit[j + 1] - vinit[i]);
}
if (i != 1 && vinit[i] < vinit[i - 1] && vinit[i - 1] - vinit[i] >= vinit[j + 1] - vinit[i]){
muchie (i , j , j + 1 , i - 1 , vinit[j + 1] - vinit[i]);
}
/// cazuri particulare de egalitate??
}
else { /// segm e descrescator
if (i != n){ /// ma duc in nodul i + 1, deci nu parasesc segm
if (vinit[i + 1] > vinit[i] && vinit[i + 1] <= vinit[j]){
muchie (i , j , i + 1 , j , vinit[i + 1] - vinit[i]); /// se pastreaza segmentul
}
else if (vinit[i + 1] < vinit[i] && vinit[i + 1] >= vinit[j + 1]){
muchie (i , j , i + 1 , j , vinit[i] - vinit[i + 1]);
}
}
if (i != 1){ /// ma duc in nodul i - 1, raman pe acelasi segm
if (vinit[i - 1] > vinit[i] && vinit[i - 1] <= vinit[j]){
muchie (i , j , i - 1 , j , vinit[i - 1] - vinit[i]); /// se pastreaza segmentul
}
else if (vinit[i - 1] < vinit[i] && vinit[i - 1] >= vinit[j + 1]){
muchie (i , j , i - 1 , j , vinit[i] - vinit[i - 1]);
}
}
/// --------------------------------------------------
/// sunt intre j si j + 1
/// vinitreau sa ma mut in j, adc URC
if (i != n && vinit[i] < vinit[i + 1] && vinit[i + 1] - vinit[i] >= vinit[j] - vinit[i]){
muchie (i , j , j , i , vinit[j] - vinit[i]);
}
if (i != 1 && vinit[i] < vinit[i - 1] && vinit[i - 1] - vinit[i] >= vinit[j] - vinit[i]){
muchie (i , j , j , i - 1 , vinit[j] - vinit[i]);
}
/// vinitreau sa ma duc in j + 1 adica cobor
if (i != n && vinit[i] > vinit[i + 1] && vinit[i] - vinit[i + 1] >= vinit[i] - vinit[j + 1]){
muchie (i , j , j + 1 , i , vinit[i] - vinit[j + 1]);
}
if (i != 1 && vinit[i] > vinit[i - 1] && vinit[i] - vinit[i - 1] >= vinit[i] - vinit[j + 1]){
muchie (i , j , j + 1 , i - 1 ,vinit[i] - vinit[j + 1]);
}
}
}
}
}
/// am construit graful vietii
for (i = 0 ; i < n * n ; i++)
dp[i] = 2000000000;
dp[encode(1 , n - 1)] = 0;
h.push(make_pair(0 , encode(1 , n - 1)));
while (!h.empty()){
cost = -h.top().first;
nod = h.top().second;
h.pop();
actual = decode(nod);
//printf ("%d %d\n",actual.first , actual.second);
if (actual.first == actual.second || actual.first == actual.second + 1){
fprintf (fout,"%d",cost);
return 0;
}
if (dp[nod] != cost)
continue;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
val = v[nod][i].second;
if (dp[vecin] > dp[nod] + val){
dp[vecin] = dp[nod] + val;
h.push(make_pair(-dp[vecin] , vecin));
}
}
}
fprintf (fout,"NO");
return 0;
}
Compilation message
climbers.cpp: In function 'int main()':
climbers.cpp:228:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for (i = 0 ; i < v[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
climbers.cpp:35:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
35 | fscanf (fin,"%d",&n);
| ~~~~~~~^~~~~~~~~~~~~
climbers.cpp:37:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | fscanf (fin,"%d",&vinit[i]);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
235372 KB |
Output is correct |
| 2 |
Correct |
154 ms |
237292 KB |
Output is correct |
| 3 |
Correct |
208 ms |
257724 KB |
Output is correct |
| 4 |
Incorrect |
688 ms |
438124 KB |
Output isn't correct |
| 5 |
Execution timed out |
832 ms |
524288 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
235264 KB |
Output is correct |
| 2 |
Incorrect |
162 ms |
235300 KB |
Output isn't correct |
| 3 |
Correct |
151 ms |
235756 KB |
Output is correct |
| 4 |
Correct |
155 ms |
235372 KB |
Output is correct |
| 5 |
Incorrect |
157 ms |
238316 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
235600 KB |
Output isn't correct |
| 2 |
Correct |
162 ms |
238060 KB |
Output is correct |
| 3 |
Incorrect |
393 ms |
285676 KB |
Output isn't correct |
| 4 |
Execution timed out |
959 ms |
524292 KB |
Time limit exceeded |
| 5 |
Execution timed out |
930 ms |
524292 KB |
Time limit exceeded |
| 6 |
Execution timed out |
828 ms |
524292 KB |
Time limit exceeded |
| 7 |
Runtime error |
781 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
715 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
682 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
686 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
