Submission #203739

#	Time	Username	Problem	Language	Result	Execution time	Memory
203739		EntityIT	Sparklers (JOI17_sparklers)	C++14	0 / 100	5 ms	376 KiB

sparklers

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, k, t; cin >> n >> k >> t; --k;
  vector<int> x(n);
  for (auto &i : x) cin >> i;

  auto check = [&](int s) {
    int l = k, r = k;
    while (l || r ^ (n - 1) ) {
      if (!l) {
        ++r;
        if ( (x[r] - x[l] + t - 1) / t > 2LL * s * (r - l) ) return false;
      }
      else if (!(r ^ (n - 1) ) ) {
        --l;
        if ( (x[r] - x[l] + t - 1) / t > 2LL * s * (r - l) ) return false;
      }
      else {
        if (x[r + 1] - x[r] < x[l] - x[l - 1]) {
          ++r;
          if ( (x[r] - x[l] + t - 1) / t > 2LL * s * (r - l) ) return false;
        }
        else {
          --l;
          if ( (x[r] - x[l] + t - 1) / t > 2LL * s * (r - l) ) return false;
        }
      }
    }
    return true;
  };

  int l = 0, r = x.back();
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid) ) r = mid;
    else l = mid + 1;
  }

  cout << l << '\n';

  return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50