oj.uz

Submission #24309

# Submission time Handle Problem Language Result Execution time Memory
24309 2017-06-04T14:54:40 Z jiaqiyang Sparklers (JOI17_sparklers) C++14
0 / 100
 0 ms 1564 KB 
#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);
  i64 val = 0;
  if (u.back().second < 0) val += u.back().second, u.pop_back();
  if (v.back().second < 0) val += v.back().second, v.pop_back();
  i64 cur = 0;
  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 (cur + v.back().first >= 0) {
      cur += v.back().second;
      v.pop_back();
    } else {
      return false;
    }
  }
  return cur + val >= 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1564 KB Output is correct
2 Correct 0 ms 1564 KB Output is correct
3 Incorrect 0 ms 1564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1564 KB Output is correct
2 Correct 0 ms 1564 KB Output is correct
3 Incorrect 0 ms 1564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1564 KB Output is correct
2 Correct 0 ms 1564 KB Output is correct
3 Incorrect 0 ms 1564 KB Output isn't correct
4 Halted 0 ms 0 KB -