Submission #24317

#	Time	Username	Problem	Language	Result	Execution time	Memory
24317		jiaqiyang	Sparklers (JOI17_sparklers)	C++14	100 / 100	89 ms	7544 KiB

sparklers

#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>

typedef long long i64;

const int N = 100000 + 10;
const i64 INF = 1LL << 60;

int n, k, t, x[N];

auto calc(std::vector<i64> &cur) {
  const int tot = cur.size();
  std::vector<std::pair<i64, i64>> res;
  for (int i = 0; i < tot;) {
    i64 sum = 0, min = 0;
    int j = i;
    while (j < tot) {
      min = std::min(min, sum += cur[j++]);
      if (sum >= 0) break;
    }
    if (sum >= 0) res.emplace_back(min, sum);
    if (j == tot) cur.erase(cur.begin(), cur.begin() + (sum < 0 ? i : j));
    i = j;
  }
  return res;
}

bool check(std::vector<std::pair<i64, i64>> &u, std::vector<std::pair<i64, i64>> &v, i64 cur) {
  std::reverse(u.begin(), u.end());
  std::reverse(v.begin(), v.end());
  while (!(u.empty() && v.empty())) {
    if (!u.empty() && cur + u.back().first >= 0) {
      cur += u.back().second;
      u.pop_back();
    } else if (!v.empty() && cur + v.back().first >= 0) {
      cur += v.back().second;
      v.pop_back();
    } else {
      return false;
    }
  }
  return true;
}

bool solve(int s) {
  std::vector<i64> a, b;
  for (int i = k; i > 1; --i) a.push_back(2LL * t * s - (x[i] - x[i - 1]));
  for (int i = k; i < n; ++i) b.push_back(2LL * t * s - (x[i + 1] - x[i]));
  i64 temp = std::accumulate(a.begin(), a.end(), std::accumulate(b.begin(), b.end(), 0LL));
  if (temp < 0) return false;
  auto u = calc(a), v = calc(b);
  if (!check(u, v, 0)) return false;
  std::reverse(a.begin(), a.end());
  std::reverse(b.begin(), b.end());
  for (auto &i : a) i = -i;
  for (auto &i : b) i = -i;
  u = calc(a), v = calc(b);
  return check(u, v, temp);
}

int main() {
  scanf("%d%d%d", &n, &k, &t);
  for (int i = 1; i <= n; ++i) scanf("%d", &x[i]);
  int l = 0, r = x[n];
  while (l < r) {
    int mid = (l + r) >> 1;
    if (solve(mid)) r = mid; else l = mid + 1;
  }
  printf("%d\n", l);
  return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:64:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &k, &t);
                              ^
sparklers.cpp:65:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; ++i) scanf("%d", &x[i]);
                                                  ^

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