Submission #528941

#TimeUsernameProblemLanguageResultExecution timeMemory
528941tabrMountains (IOI17_mountains)C++17
70 / 100
1067 ms16056 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif int maximum_deevs(vector<int> y) { int n = (int) y.size(); vector<vector<int>> dp(n + 1, vector<int>(n + 1)); for (int l = n - 1; l >= 0; l--) { for (int r = l + 1; r <= n; r++) { int pos = (int) (max_element(y.begin() + l, y.begin() + r) - y.begin()); dp[l][r] = 1; int lst = pos; pair<int, int> a = make_pair(1, 0); for (int i = pos - 1; i >= l; i--) { auto b = make_pair(y[pos] - y[i], pos - i); if (1LL * a.first * b.second >= 1LL * a.second * b.first) { a = b; dp[l][r] += dp[i + 1][lst]; lst = i; } } dp[l][r] += dp[l][lst]; lst = pos; a = make_pair(1, 0); for (int i = pos + 1; i < r; i++) { auto b = make_pair(y[pos] - y[i], i - pos); if (1LL * a.first * b.second >= 1LL * a.second * b.first) { a = b; dp[l][r] += dp[lst + 1][i]; lst = i; } } dp[l][r] += dp[lst + 1][r]; dp[l][r] = max(dp[l][r], dp[l][pos] + dp[pos + 1][r]); } } return dp[0][n]; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); debug(maximum_deevs({6, 1, 5, 2, 3, 1})); debug(maximum_deevs({0, 1, 2})); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...