Submission #24312

#	Time	Username	Problem	Language	Result	Execution time	Memory
24312		jiaqiyang	Sparklers (JOI17_sparklers)	C++14	0 / 100	0 ms	1564 KiB

sparklers

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

typedef long long i64;

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

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

auto calc(const 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;
    }
    i = j;
    res.emplace_back(min, sum);
  }
  return res;
}

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]));
  auto u = calc(a), v = calc(b);
  auto p = u.back(), q = v.back();
  if (p.second < 0) u.pop_back(); else p = {0, 0};
  if (q.second < 0) v.pop_back(); else q = {0, 0};
  std::reverse(u.begin(), u.end());
  std::reverse(v.begin(), v.end());
  i64 cur = 0;
  while (!(u.empty() && v.empty())) {
    if (!u.empty() && cur + u.back().first >= 0) {
      cur += u.back().second;
      u.pop_back();
    } else if (cur + v.back().first >= 0) {
      cur += v.back().second;
      v.pop_back();
    } else {
      return false;
    }
  }
  return (cur + p.first >= 0 && cur + p.second + q.first >= 0) || (cur + q.first >= 0 && cur + q.second + p.first >= 0);
}

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:54: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:55: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: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50