제출 #1217846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217846		abczz	Sparklers (JOI17_sparklers)	C++20	100 / 100	72 ms	6400 KiB

sparklers

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <ll> A, B, tmpa, tmpb;
ll n, k, t, l, r, mid, X[100000];

bool check(ll u, ll ty) {
  ll p = -1e18, mn = 1e18;
  vector <array<ll, 2>> X, Y;
  if (ty) {
    X.push_back({0, (ll)1e18});
    Y.push_back({0, (ll)1e18});
    p = 0;
  }
  for (ll i=0; i<tmpa.size(); ++i) {
    mn = min(mn, tmpa[i]);
    if (p < tmpa[i] || (p == tmpa[i] && !ty)) {
      p = tmpa[i];
      X.push_back({p, mn});
      mn = 1e18;
    }
  }
  if (p < 0) X.push_back({0, (ll)1e18});
  p = -1e18, mn = 1e18;
  if (ty) p = 0;
  for (ll i=0; i<tmpb.size(); ++i) {
    mn = min(mn, tmpb[i]);
    if (p < tmpb[i] || (p == tmpb[i] && !ty)) {
      p = tmpb[i];
      Y.push_back({p, mn});
      mn = 1e18;
    }
  }
  if (p < 0) Y.push_back({0, (ll)1e18});
  int i = 0, j = 0;
  while (i < (ll)X.size()-1 || j < (ll)Y.size()-1) {
    if (i < (ll)X.size()-1 && Y[j][0]+X[i+1][1] >= 0) ++i;
    else if (j < (ll)Y.size()-1 && X[i][0]+Y[j+1][1] >= 0) ++j;
    else break;
  }
  if (i < (ll)X.size()-1 || j < (ll)Y.size()-1) return 0;
  return 1;
}
bool solve(ll u) {
  u *= 2;
  for (ll i=0; i<A.size(); ++i) tmpa[i] = (i+1)*u - A[i];
  for (ll i=0; i<B.size(); ++i) tmpb[i] = (i+1)*u - B[i];
  bool ok = check(u, 1);
  reverse(tmpa.begin(), tmpa.end());
  reverse(tmpb.begin(), tmpb.end());
  return ok & check(u, 0) & ((tmpa.empty() ? 0 : tmpa[0]) + (tmpb.empty() ? 0 : tmpb[0]) >= 0);
}
int main() {
  cin >> n >> k >> t;
  --k;
  for (int i=0; i<n; ++i) cin >> X[i];
  for (int i=k-1; i>=0; --i) A.push_back(X[k]-X[i]);
  for (int i=k+1; i<n; ++i) B.push_back(X[i]-X[k]);
  tmpa.resize(A.size());
  tmpb.resize(B.size());
  l = 0, r = ((ll)1e9+t-1)/t;
  while (l < r) {
    mid = (l+r)/2;
    if (solve(mid*t)) r = mid;
    else l = mid+1;
  }
  cout << l << '\n';
}

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