Submission #676706

#TimeUsernameProblemLanguageResultExecution timeMemory
676706sugartheanhClimbers (RMI18_climbers)C++14
100 / 100
316 ms196060 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second #define ld long double const ll maxn = 5e3 + 1, maxm = 1e6 + 1; const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 31, base = 1000050017, biginf = 5e18; const ld eps = 1e-9; int n; int a[maxn]; ll dp[maxn][maxn]; set<pair<ll, pair<int, int>>> setik; vector<int> vec; bool is(int i, int j){ if (a[j] <= a[j + 1]){ return (a[j] <= a[i] && a[i] <= a[j + 1]); } else{ return (a[j] >= a[i] && a[i] >= a[j + 1]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; ++i){ cin >> a[i]; } vec.pb(a[1]); for (int i = 2; i < n; ++i){ if (a[i] < a[i - 1] && a[i] < a[i + 1] || a[i - 1] < a[i] && a[i] > a[i + 1]){ vec.pb(a[i]); } } for (int i = 1; i <= n; ++i){ a[i] = 0; } vec.pb(a[n]); n = (int)vec.size(); for (int i = 0; i < n; ++i){ a[i + 1] = vec[i]; } for (int i = 1; i <= n; ++i){ for (int j = 1; j <= n; ++j){ dp[i][j] = inf * inf; } } dp[1][n - 1] = 0; setik.insert(mp(0, mp(1, n - 1))); while (setik.size() > 0){ pair<ll, pair<int, int>> cur = *setik.begin(); setik.erase(cur); ll cost = cur.f, x = cur.s.f, y = cur.s.s; if (x == y || x == y + 1){ cout << cost; exit(0); } if (cost > dp[x][y]) continue; if (x > 1 && is(x - 1, y) && dp[x - 1][y] > dp[x][y] + abs(a[x] - a[x - 1])){ dp[x - 1][y] = dp[x][y] + abs(a[x] - a[x - 1]); setik.insert(mp(dp[x - 1][y], mp(x - 1, y))); } if (x < n && is(x + 1, y) && dp[x + 1][y] > dp[x][y] + abs(a[x] - a[x + 1])){ dp[x + 1][y] = dp[x][y] + abs(a[x] - a[x + 1]); setik.insert(mp(dp[x + 1][y], mp(x + 1, y))); } if (is(y, x) && dp[y][x] > dp[x][y] + abs(a[x] - a[y])){ dp[y][x] = dp[x][y] + abs(a[x] - a[y]); setik.insert(mp(dp[y][x], mp(y, x))); } if (x > 1 && is(y, x - 1) && dp[y][x - 1] > dp[x][y] + abs(a[x] - a[y])){ dp[y][x - 1] = dp[x][y] + abs(a[x] - a[y]); setik.insert(mp(dp[y][x - 1], mp(y, x - 1))); } if (is(y + 1, x) && dp[y + 1][x] > dp[x][y] + abs(a[x] - a[y + 1])){ dp[y + 1][x] = dp[x][y] + abs(a[x] - a[y + 1]); setik.insert(mp(dp[y + 1][x], mp(y + 1, x))); } if (is(y + 1, x - 1) && dp[y + 1][x - 1] > dp[x][y] + abs(a[x] - a[y + 1])){ dp[y + 1][x - 1] = dp[x][y] + abs(a[x] - a[y + 1]); setik.insert(mp(dp[y + 1][x - 1], mp(y + 1, x - 1))); } } cout << "NO\n"; }

Compilation message (stderr)

climbers.cpp: In function 'int main()':
climbers.cpp:38:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |         if (a[i] < a[i - 1] && a[i] < a[i + 1] || a[i - 1] < a[i] && a[i] > a[i + 1]){
      |             ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...