Submission #1197388

#TimeUsernameProblemLanguageResultExecution timeMemory
1197388og_matveychick1Sparklers (JOI17_sparklers)C++20
50 / 100
160 ms16260 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll N = 1e3 + 5; ll n, k, t, a[N]; pair<ll, ll> dp[N][N]; void update(ll l, ll r, pll x, pll y) { pll b = {max(x.first, y.first), min(x.second, y.second)}; if (b.first > b.second) return; if (dp[l][r].first < b.first) return; dp[l][r].first = min(dp[l][r].first, b.first); dp[l][r].second = max(dp[l][r].second, b.second); } bool check(ll s) { if (s * t > 1e9) return 1; for (ll i = 0; i < N; i++) for (ll j = 0; j < N; j++) dp[i][j] = {1e18, -1e18}; dp[k][k] = {a[k], a[k]}; for (ll d = 1; d < n; d++) { for (ll l = 0, r = l + d - 1; r < n; l++, r++) { if (r != n - 1) { update(l, r + 1, {dp[l][r].first - t * s, dp[l][r].second + t * s}, {a[r + 1] - d * t * s, a[r + 1] + d * t * s}); } if (l - 1 != -1) { update(l - 1, r, {dp[l][r].first - t * s, dp[l][r].second + t * s}, {a[l - 1] - d * t * s, a[l - 1] + d * t * s}); } } } return dp[0][n - 1].second - dp[0][n - 1].first >= 0; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> k >> t, k--; for (ll i = 0; i < n; i++) cin >> a[i]; ll l = -1, r = 1e9 / t + 5; check(38); while (l + 1 < r) { ll m = (l + r) / 2; (check(m) ? r : l) = m; } cout << r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...