| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126093 | caterpillow | Mountains (IOI17_mountains) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<ll> h;
vector<vector<pair<int, int>>> ranges;
vector<vector<int>> memo;
int dp(int l, int r, int best) {
if (r < l || l < 0) return 0;
if ((r - l) / 2 < best) return 0;
if (memo[l][r] != -1) return memo[l][r];
int res = 1;
for (auto [lo, hi] : ranges[r]) {
if (hi < l) continue;
lo = max(lo, l);
res += dp(lo, hi, -1);
}
return memo[l][r] = max(res, dp(l, r - 1, res));
}
int maximum_deevs(vector<int> y) {
n = y.size();
h.resize(n);
ranges.resize(n);
for (int i = 0; i < n; i++) h[i] = y[i];
for (int r = 1; r < n; r++) {
int highest = r - 1;
for (int i = r - 2; i >= 0; i--) {
pair<ll, ll> vec1 = {i - r, h[i] - h[r]};
pair<ll, ll> vec2 = {highest - r, h[highest] - h[r]};
ll x = vec1.first * vec2.second;
ll y = vec1.second * vec2.first;
if (x - y >= 0) {
if (i + 1 <= highest - 1) ranges[r].push_back({i + 1, highest - 1});
highest = i;
}
}
if (highest) ranges[r].push_back({0, highest - 1});
}
memo.resize(n, vector<int>(n, -1));
return dp(0, n - 1, -1);
}
#ifdef LOCAL
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> y(n);
for (int i = 0; i < n; i++) {
assert(1 == scanf("%d", &y[i]));
}
int result = maximum_deevs(y);
printf("%d\n", result);
return 0;
}
#endif