| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1358696 | lyra_g13 | Radio Towers (IOI22_towers) | C++20 | 0 ms | 0 KiB |
#include "towers.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int n;
vector<ll> h;
void init(int N, vector<ll> H) {
n = N;
h = H;
};
int max_towers(int l, int r, int d) {
ll ans = 1;
vector<ll> dp(n, 1);
for (int i = l; i <= r; i++) {
dp[i] = 1;
ll mid = 0;
for (int j = i - 1; j >= l; j--) {
if (j + 1 < i)
mid = max(mid, h[j + 1]);
ll bound = max(h[j], h[i]) + d;
if (mid >= bound)
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
return ans;
};