제출 #168997

#제출 시각아이디문제언어결과실행 시간메모리
168997combi1k1Sparklers (JOI17_sparklers)C++14
100 / 100
29 ms2564 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int k; cin >> k; int T; cin >> T; k--; vector<int> v(n); vector<ll> d(n); auto check = [&](int m) { for(int i = 0 ; i < n ; ++i) d[i] = 2ll * T * i * m - v[i]; int pl = k, nl = k - 1; int pr = k, nr = k + 1; while (1) { while (d[nl] > d[pl] && d[nl] <= d[pr] && nl > 0) nl--; while (d[nr] < d[pr] && d[nr] >= d[pl] && nr < n - 1) nr++; bool ok = 0; if (nl >= 0 && d[nl] <= d[pl]) pl = nl--, ok = 1; if (nr < n && d[nr] >= d[pr]) pr = nr++, ok = 1; if(!ok) break; } if (nr < n && d[pl] > d[nr]) return false; if (nl >= 0 && d[pr] < d[nl]) return false; int l = 0; nl = 1; int r = n - 1; nr = n - 2; while (1) { while (d[nl] > d[l] && d[nl] <= d[r] && nl < k) nl++; while (d[nr] < d[r] && d[nr] >= d[l] && nr > k) nr--; bool ok = 0; if (nl <= k && d[nl] <= d[l]) l = nl++, ok = 1; if (nr >= k && d[nr] >= d[r]) r = nr--, ok = 1; if(!ok) break; } return pl <= l && r <= pr; }; for(int&x : v) cin >> x; int l = 0; int r = 1e9; for(; l < r ;) { int m = (l + r) / 2; if (check(m)) r = m; else l = m + 1; } cout << l << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...