Submission #749107

#TimeUsernameProblemLanguageResultExecution timeMemory
749107TheOpChickenSparklers (JOI17_sparklers)C++17
0 / 100
1 ms212 KiB
#include <iostream> using namespace std; const long long maxN = 1e5 + 5, inf = 1e9; long long arr[maxN]; int main(){ long long n, k, t; cin >> n >> k >> t; k--; for (int i = 0; i < n; i++) cin >> arr[i]; long long l = 1, r = inf/t + 5, ans = inf/t + 5; while(l <= r){ long long mid = (l+r)/2, left_margin = inf, right_margin = inf, left_end = 0, right_end = 0; for (int i = k-1; i >= 0; i--){ long long last = arr[k] - (k-i)*2*mid*t; if (last < -inf){ left_end = inf; break; } long long diff = arr[i] - last; left_margin = min(left_margin, diff); if (i == 0) left_end = diff; } for (int i = k+1; i < n; i++){ long long last = arr[k] + (i-k)*2*mid*t; if (last > 2*inf){ right_end = inf; break; } long long diff = last - arr[i]; right_margin = min(right_margin, diff); if (i == n-1) right_end = diff; } if ((left_margin >= 0 && left_end + right_margin >= 0) || (right_margin >= 0 && right_end + left_margin >= 0)){ ans = mid; r = mid-1; } else l = mid+1; } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...