oj.uz

Submission #24315

# Submission time Handle Problem Language Result Execution time Memory
24315 2017-06-04T15:58:21 Z jiaqiyang Sparklers (JOI17_sparklers) C++14
0 / 100
 0 ms 1564 KB 
#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 (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

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
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 Runtime error 0 ms 1564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 Runtime error 0 ms 1564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 Runtime error 0 ms 1564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -