Submission #257360

#TimeUsernameProblemLanguageResultExecution timeMemory
257360FischerMountains (IOI17_mountains)C++14
100 / 100
52 ms16256 KiB
#include "mountains.h" #include <bits/stdc++.h> int maximum_deevs(std::vector<int> y) { int n = y.size(); std::vector<int> last(n, -1); std::vector<std::vector<int>> memo(n+1, std::vector<int>(n+1, 0)); for (int i = 0; i < n; ++i) { memo[i][i] = 1; } for (int len = 2; len <= n; ++len) { for (int i = 0; i < n; ++i) { int nxt = i + len - 1; if (nxt >= n) continue; memo[i][nxt] = memo[i+1][nxt]; if (last[i] == -1 || (last[i] - i) *1ll* (y[nxt] - y[i]) >= (nxt - i) *1ll* (y[last[i]] - y[i])) { last[i] = nxt; } memo[i][nxt] = std::max(memo[i][nxt], memo[i][last[i]-1] + memo[last[i]+1][nxt]); } } return memo[0][n-1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...