Submission #754853

#TimeUsernameProblemLanguageResultExecution timeMemory
754853boris_mihovMountains (IOI17_mountains)C++17
0 / 100
1 ms212 KiB
#include "mountains.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 2000 + 10; int n; int a[MAXN]; int rec(int l, int r) { if (l > r) { return 0; } if (l == r) { return 1; } std::vector <int> max; max.push_back(l - 1); int val = a[l]; for (int i = l + 1 ; i <= r ; ++i) { val = std::max(val, a[i]); } for (int i = l ; i <= r ; ++i) { if (val == a[i]) { max.push_back(i); } } int res = 0; max.push_back(r + 1); bool add = false; for (int i = 0 ; i < (int)max.size() - 1 ; ++i) { if (i > 0 && max[i - 1] == max[i] && max[i] == max[i + 1]) { add = true; } res += rec(max[i] + 1, max[i + 1] - 1); } res += add; res = std::max(res, (int)max.size() - 2); return res; } int maximum_deevs(std::vector <int> y) { n = y.size(); for (int i = 1 ; i <= n ; ++i) { a[i] = y[i - 1]; } return rec(1, n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...