답안 #341790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341790	2020-12-31T04:07:20 Z	KoD	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	720 ms	172992 KB

bulldozer

#line 1 "main.cpp"

/**
 * @title Template
 */

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <map>

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"

class range {
  struct iter {
    std::size_t itr;
    constexpr iter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { ++itr; }
    constexpr bool operator != (iter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  struct reviter {
    std::size_t itr;
    constexpr reviter(std::size_t pos) noexcept: itr(pos) { }
    constexpr void operator ++ () noexcept { --itr; }
    constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; }
    constexpr std::size_t operator * () const noexcept { return itr; }
  };

  const iter first, last;

public:
  constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { }
  constexpr iter begin() const noexcept { return first; }
  constexpr iter end() const noexcept { return last; }
  constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } 
  constexpr reviter rend() const noexcept { return reviter(*first - 1); } 
};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp"

#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/monoid.cpp"

#include <type_traits>
#line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/other/monoid.cpp"
#include <stdexcept>

template <class T, class = void>
class has_identity: public std::false_type { };

template <class T>
class has_identity<T, typename std::conditional<false, decltype(T::identity()), void>::type>: public std::true_type { };

template <class T>
constexpr typename std::enable_if<has_identity<T>::value, typename T::type>::type empty_exception() {
  return T::identity();
}
template <class T>
[[noreturn]] typename std::enable_if<!has_identity<T>::value, typename T::type>::type empty_exception() {
  throw std::runtime_error("type T has no identity");
}

template <class T, bool HasIdentity>
class fixed_monoid_impl: public T {
public:
  using type = typename T::type;

  static constexpr type convert(const type &value) { return value; }
  static constexpr type revert(const type &value) { return value; }

  template <class Mapping, class Value, class... Args>
  static constexpr void operate(Mapping &&func, Value &value, const type &op, Args&&... args) {
    value = func(value, op, std::forward<Args>(args)...);
  }
  template <class Constraint>
  static constexpr bool satisfies(Constraint &&func, const type &value) {
    return func(value);
  }
};

template <class T>
class fixed_monoid_impl<T, false> {
public:
  class type {
  public:
    typename T::type value;
    bool state;
  
    explicit constexpr type(): value(typename T::type { }), state(false) { }
    explicit constexpr type(const typename T::type &value): value(value), state(true) { }
  };

  static constexpr type convert(const typename T::type &value) { return type(value); }
  static constexpr typename T::type revert(const type &value) { 
    if (!value.state) throw std::runtime_error("attempted to revert identity to non-monoid"); 
    return value.value; 
  }

  static constexpr type identity() { return type(); }
  static constexpr type operation(const type &v1, const type &v2) {
    if (!v1.state) return v2;
    if (!v2.state) return v1;
    return type(T::operation(v1.value, v2.value));
  }

  template <class Mapping, class Value, class... Args>
  static constexpr void operate(Mapping &&func, Value &value, const type &op, Args&&... args) {
    if (!op.state) return;
    value = func(value, op.value, std::forward<Args>(args)...);
  }
  template <class Constraint>
  static constexpr bool satisfies(Constraint &&func, const type &value) {
    if (!value.state) return false;
    return func(value.value);
  }
};

template <class T>
using fixed_monoid = fixed_monoid_impl<T, has_identity<T>::value>;

/**
 * @title Monoid Utility
 */
#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/bit_operation.cpp"

#include <cstddef>
#include <cstdint>

constexpr size_t bit_ppc(const uint64_t x) { return __builtin_popcountll(x); }
constexpr size_t bit_ctzr(const uint64_t x) { return x == 0 ? 64 : __builtin_ctzll(x); }
constexpr size_t bit_ctzl(const uint64_t x) { return x == 0 ? 64 : __builtin_clzll(x); }
constexpr size_t bit_width(const uint64_t x) { return 64 - bit_ctzl(x); }
constexpr uint64_t bit_msb(const uint64_t x) { return x == 0 ? 0 : uint64_t(1) << (bit_width(x) - 1); }
constexpr uint64_t bit_lsb(const uint64_t x) { return x & (-x); }
constexpr uint64_t bit_cover(const uint64_t x) { return x == 0 ? 0 : bit_msb(2 * x - 1); }

constexpr uint64_t bit_rev(uint64_t x) {
  x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);
  x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
  x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4);
  x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8);
  x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16);
  x = (x >> 32) | (x << 32);
  return x;
}

/**
 * @title Bit Operations
 */
#line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp"

#line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp"
#include <iterator>
#line 11 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp"
#include <type_traits>
#line 13 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp"

template <class Monoid>
class segment_tree {
public:
  using structure    = Monoid;
  using value_monoid = typename Monoid::value_structure;
  using value_type   = typename Monoid::value_structure::type;
  using size_type    = size_t;

private:
  using fixed_value_monoid = fixed_monoid<value_monoid>;
  using fixed_value_type   = typename fixed_value_monoid::type;

  std::vector<fixed_value_type> M_tree;

  void M_fix_change(const size_type index) {
    M_tree[index] = fixed_value_monoid::operation(M_tree[index << 1 | 0], M_tree[index << 1 | 1]);
  }

public:
  segment_tree() = default;
  explicit segment_tree(const size_type size) { initialize(size); }
  template <class InputIterator>
  explicit segment_tree(InputIterator first, InputIterator last) { construct(first, last); }

  void initialize(const size_type size) {
    clear();
    M_tree.assign(size << 1, fixed_value_monoid::identity());
  }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) {
    clear();
    const size_type size = std::distance(first, last);
    M_tree.reserve(size << 1);
    M_tree.assign(size, fixed_value_monoid::identity());
    std::transform(first, last, std::back_inserter(M_tree), [&](const value_type &value) {
      return fixed_value_monoid::convert(value);
    });
    for (size_type index = size - 1; index != 0; --index) {
      M_fix_change(index);
    }
  }

  void assign(size_type index, const value_type &value) {
    assert(index < size());
    index += size();
    M_tree[index] = fixed_value_monoid::convert(value);
    while (index != 1) {
      index >>= 1;
      M_fix_change(index);
    } 
  }

  value_type at(const size_type index) const { 
    assert(index < size());
    return fixed_value_monoid::revert(M_tree[index + size()]);
  }

  value_type fold(size_type first, size_type last) const {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    fixed_value_type fold_l = fixed_value_monoid::identity();
    fixed_value_type fold_r = fixed_value_monoid::identity();
    while (first != last) {
      if (first & 1) {
        fold_l = fixed_value_monoid::operation(fold_l, M_tree[first]);
        ++first;
      }
      if (last & 1) {
        --last;
        fold_r = fixed_value_monoid::operation(M_tree[last], fold_r);      
      }
      first >>= 1;
      last >>= 1;
    }
    return fixed_value_monoid::revert(fixed_value_monoid::operation(fold_l, fold_r));
  }

  template <bool ToRight = true, class Constraint, std::enable_if_t<ToRight>* = nullptr> 
  size_type satisfies(const size_type left, Constraint &&func) const {
    assert(left <= size());
    if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), 
      fixed_value_monoid::identity())) return left;
    size_type first = left + size();
    size_type last = 2 * size();
    const size_type last_c = last;
    fixed_value_type fold = fixed_value_monoid::identity();
    const auto try_merge = [&](const size_type index) {
      fixed_value_type tmp = fixed_value_monoid::operation(fold, M_tree[index]);
      if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), tmp)) return true;
      fold = std::move(tmp);
      return false;
    };
    const auto subtree = [&](size_type index) {
      while (index < size()) {
        index <<= 1;
        if (!try_merge(index)) ++index;
      }
      return index - size() + 1;
    };
    size_type story = 0;
    while (first < last) {
      if (first & 1) {
        if (try_merge(first)) return subtree(first);
        ++first;
      }
      first >>= 1;
      last >>= 1;
      ++story;
    }
    while (story--) {
      last = last_c >> story;
      if (last & 1) {
        --last;
        if (try_merge(last)) return subtree(last);
      }
    }
    return size() + 1;
  }

  template <bool ToRight = true, class Constraint, std::enable_if_t<!ToRight>* = nullptr> 
  size_type satisfies(const size_type right, Constraint &&func) const {
    assert(right <= size());
    if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), 
      fixed_value_monoid::identity())) return right;
    size_type first = size();
    size_type last = right + size();
    const size_type first_c = first;
    fixed_value_type fold = fixed_value_monoid::identity();
    const auto try_merge = [&](const size_type index) {
      fixed_value_type tmp = fixed_value_monoid::operation(M_tree[index], fold);
      if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), tmp)) return true;
      fold = std::move(tmp);
      return false;
    };
    const auto subtree = [&](size_type index) {
      while (index < size()) {
        index <<= 1;
        if (try_merge(index + 1)) ++index;
      }
      return index - size();
    };
    size_type story = 0;
    while (first < last) {
      if (first & 1) ++first;
      if (last & 1) {
        --last;
        if (try_merge(last)) return subtree(last);
      }
      first >>= 1;
      last >>= 1;
      ++story;
    }
    const size_type cover = bit_cover(first_c);
    while (story--) {
      first = (cover >> story) - ((cover - first_c) >> story);
      if (first & 1) {
        if (try_merge(first)) return subtree(first);
      }
    }
    return size_type(-1);
  }

  void clear() {
    M_tree.clear();
    M_tree.shrink_to_fit();
  }
  size_type size() const { 
    return M_tree.size() >> 1;
  }
};

/**
 * @title Segment Tree
 */
#line 17 "main.cpp"

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr i32 inf32 = (u32) ~0 >> 2;
constexpr i64 inf64 = (u64) ~0 >> 2;

struct st_monoid {
  struct value_structure {
    struct type {
      i64 max, min, dif;
      explicit type(const i64 value): max(value), min(value), dif(0) { }
      explicit type(const i64 max, const i64 min, const i64 dif): max(max), min(min), dif(dif) { }
    };
    static type identity() { return type(-inf64, inf64, -inf64); }
    static type operation(const type& v1, const type& v2) { 
      return type(std::max(v1.max, v2.max), std::min(v1.min, v2.min), std::max({ v2.max - v1.min, v1.dif, v2.dif}));
    }
  };
};

template <class T>
using Vec = std::vector<T>;

struct Frac {
  i64 a, b;

  Frac(const i64 x, const i64 y): a(x), b(y) {
    if (b < 0) {
      a = -a;
      b = -b;
    }
  }
  
  bool operator < (const Frac &other) const {
    return a * other.b < other.a * b;
  }
  bool operator > (const Frac &other) const {
    return a * other.b > other.a * b;
  }
  bool operator == (const Frac &other) const {
    return a * other.b == other.a * b;
  }
};

constexpr i64 INF = 2000000005;

int main() {
  usize N;
  std::cin >> N;
  Vec<std::tuple<i32, i32, i32>> points(N);
  for (auto &[a, b, c]: points) {
    std::cin >> a >> b >> c;
  }
  std::sort(points.begin(), points.end());
  Vec<i32> X(N), Y(N), W(N);
  for (auto i: range(0, N)) {
    const auto [a, b, c] = points[i];
    X[i] = a;
    Y[i] = b;
    W[i] = c;
  }
  Vec<std::tuple<Frac, usize, usize>> vec;
  vec.reserve(N * (N - 1) / 2);
  for (auto i: range(0, N)) {
    for (auto j: range(0, i)) {
      if (X[i] != X[j]) {
        vec.emplace_back(Frac(Y[i] - Y[j], X[i] - X[j]), j, i);
      }
    }
  }
  std::sort(vec.begin(), vec.end());
  Vec<Vec<std::pair<usize, usize>>> query;
  {
    Frac last(-1, INF);
    for (const auto [f, i, j]: vec) {
      if (!(f == last)) {
        last = f;
        query.push_back({ });
      }
      query.back().emplace_back(i, j);
    }
  }
  Vec<i64> S(N + 1);
  for (auto i: range(0, N)) {
    S[i + 1] = S[i] + W[i];
  }
  using type = typename st_monoid::value_structure::type;
  segment_tree<st_monoid> seg(N + 1);
  for (auto i: range(0, N + 1)) {
    seg.assign(i, type(S[i]));
  }
  i64 ans = seg.fold(0, N + 1).dif;
  Vec<usize> inv(N);
  for (auto i: range(0, N)) {
    inv[i] = i;
  }
  for (auto &qs: query) {
    for (auto [i, j]: qs) {
      S[inv[i] + 1] = S[inv[i]] + W[j];
      seg.assign(inv[i] + 1, type(S[inv[i] + 1]));
      std::swap(inv[i], inv[j]);
    }
    ans = std::max(ans, seg.fold(0, N + 1).dif);
  }
  std::cout << ans << '\n';
  return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	2 ms	748 KB	Output is correct
4	Correct	2 ms	876 KB	Output is correct
5	Correct	2 ms	748 KB	Output is correct
6	Correct	2 ms	748 KB	Output is correct
7	Correct	2 ms	748 KB	Output is correct
8	Correct	2 ms	748 KB	Output is correct
9	Correct	2 ms	748 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	0 ms	364 KB	Output is correct
16	Correct	0 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	0 ms	364 KB	Output is correct
21	Correct	2 ms	748 KB	Output is correct
22	Correct	2 ms	748 KB	Output is correct
23	Correct	2 ms	748 KB	Output is correct
24	Correct	2 ms	748 KB	Output is correct
25	Correct	2 ms	748 KB	Output is correct
26	Correct	2 ms	748 KB	Output is correct
27	Correct	2 ms	748 KB	Output is correct
28	Correct	2 ms	748 KB	Output is correct
29	Correct	2 ms	748 KB	Output is correct
30	Correct	2 ms	748 KB	Output is correct
31	Correct	2 ms	748 KB	Output is correct
32	Correct	2 ms	748 KB	Output is correct

Subtask #3

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	2 ms	748 KB	Output is correct
4	Correct	2 ms	876 KB	Output is correct
5	Correct	2 ms	748 KB	Output is correct
6	Correct	2 ms	748 KB	Output is correct
7	Correct	2 ms	748 KB	Output is correct
8	Correct	2 ms	748 KB	Output is correct
9	Correct	2 ms	748 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	0 ms	364 KB	Output is correct
16	Correct	0 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	0 ms	364 KB	Output is correct
21	Correct	2 ms	748 KB	Output is correct
22	Correct	2 ms	748 KB	Output is correct
23	Correct	2 ms	748 KB	Output is correct
24	Correct	2 ms	748 KB	Output is correct
25	Correct	2 ms	748 KB	Output is correct
26	Correct	2 ms	748 KB	Output is correct
27	Correct	2 ms	748 KB	Output is correct
28	Correct	2 ms	748 KB	Output is correct
29	Correct	2 ms	748 KB	Output is correct
30	Correct	2 ms	748 KB	Output is correct
31	Correct	2 ms	748 KB	Output is correct
32	Correct	2 ms	748 KB	Output is correct
33	Correct	706 ms	172612 KB	Output is correct
34	Correct	694 ms	172720 KB	Output is correct
35	Correct	715 ms	172592 KB	Output is correct
36	Correct	700 ms	172592 KB	Output is correct
37	Correct	710 ms	172592 KB	Output is correct
38	Correct	704 ms	172592 KB	Output is correct
39	Correct	694 ms	172900 KB	Output is correct
40	Correct	706 ms	172720 KB	Output is correct
41	Correct	701 ms	172720 KB	Output is correct
42	Correct	696 ms	172848 KB	Output is correct
43	Correct	704 ms	172720 KB	Output is correct
44	Correct	691 ms	172720 KB	Output is correct
45	Correct	695 ms	172720 KB	Output is correct
46	Correct	704 ms	172592 KB	Output is correct
47	Correct	699 ms	172644 KB	Output is correct
48	Correct	704 ms	172764 KB	Output is correct
49	Correct	694 ms	172592 KB	Output is correct
50	Correct	698 ms	172592 KB	Output is correct
51	Correct	696 ms	172592 KB	Output is correct
52	Correct	710 ms	172772 KB	Output is correct
53	Correct	700 ms	172592 KB	Output is correct
54	Correct	696 ms	172772 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	2 ms	748 KB	Output is correct
4	Correct	2 ms	876 KB	Output is correct
5	Correct	2 ms	748 KB	Output is correct
6	Correct	2 ms	748 KB	Output is correct
7	Correct	2 ms	748 KB	Output is correct
8	Correct	2 ms	748 KB	Output is correct
9	Correct	2 ms	748 KB	Output is correct
10	Correct	2 ms	748 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	0 ms	364 KB	Output is correct
16	Correct	0 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	0 ms	364 KB	Output is correct
20	Correct	0 ms	364 KB	Output is correct
21	Correct	2 ms	748 KB	Output is correct
22	Correct	2 ms	748 KB	Output is correct
23	Correct	2 ms	748 KB	Output is correct
24	Correct	2 ms	748 KB	Output is correct
25	Correct	2 ms	748 KB	Output is correct
26	Correct	2 ms	748 KB	Output is correct
27	Correct	2 ms	748 KB	Output is correct
28	Correct	2 ms	748 KB	Output is correct
29	Correct	2 ms	748 KB	Output is correct
30	Correct	2 ms	748 KB	Output is correct
31	Correct	2 ms	748 KB	Output is correct
32	Correct	2 ms	748 KB	Output is correct
33	Correct	706 ms	172612 KB	Output is correct
34	Correct	694 ms	172720 KB	Output is correct
35	Correct	715 ms	172592 KB	Output is correct
36	Correct	700 ms	172592 KB	Output is correct
37	Correct	710 ms	172592 KB	Output is correct
38	Correct	704 ms	172592 KB	Output is correct
39	Correct	694 ms	172900 KB	Output is correct
40	Correct	706 ms	172720 KB	Output is correct
41	Correct	701 ms	172720 KB	Output is correct
42	Correct	696 ms	172848 KB	Output is correct
43	Correct	704 ms	172720 KB	Output is correct
44	Correct	691 ms	172720 KB	Output is correct
45	Correct	695 ms	172720 KB	Output is correct
46	Correct	704 ms	172592 KB	Output is correct
47	Correct	699 ms	172644 KB	Output is correct
48	Correct	704 ms	172764 KB	Output is correct
49	Correct	694 ms	172592 KB	Output is correct
50	Correct	698 ms	172592 KB	Output is correct
51	Correct	696 ms	172592 KB	Output is correct
52	Correct	710 ms	172772 KB	Output is correct
53	Correct	700 ms	172592 KB	Output is correct
54	Correct	696 ms	172772 KB	Output is correct
55	Correct	699 ms	172720 KB	Output is correct
56	Correct	705 ms	172720 KB	Output is correct
57	Correct	707 ms	172976 KB	Output is correct
58	Correct	716 ms	172644 KB	Output is correct
59	Correct	695 ms	172720 KB	Output is correct
60	Correct	699 ms	172796 KB	Output is correct
61	Correct	698 ms	172720 KB	Output is correct
62	Correct	703 ms	172720 KB	Output is correct
63	Correct	703 ms	172848 KB	Output is correct
64	Correct	693 ms	172720 KB	Output is correct
65	Correct	712 ms	172484 KB	Output is correct
66	Correct	720 ms	172592 KB	Output is correct
67	Correct	699 ms	172720 KB	Output is correct
68	Correct	698 ms	172852 KB	Output is correct
69	Correct	704 ms	172592 KB	Output is correct
70	Correct	699 ms	172592 KB	Output is correct
71	Correct	694 ms	172592 KB	Output is correct
72	Correct	694 ms	172556 KB	Output is correct
73	Correct	703 ms	172484 KB	Output is correct
74	Correct	698 ms	172672 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	2 ms	748 KB	Output is correct
17	Correct	2 ms	748 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Correct	2 ms	876 KB	Output is correct
20	Correct	2 ms	748 KB	Output is correct
21	Correct	2 ms	748 KB	Output is correct
22	Correct	2 ms	748 KB	Output is correct
23	Correct	2 ms	748 KB	Output is correct
24	Correct	2 ms	748 KB	Output is correct
25	Correct	2 ms	748 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	0 ms	364 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct
30	Correct	0 ms	364 KB	Output is correct
31	Correct	0 ms	364 KB	Output is correct
32	Correct	1 ms	364 KB	Output is correct
33	Correct	0 ms	364 KB	Output is correct
34	Correct	0 ms	364 KB	Output is correct
35	Correct	0 ms	364 KB	Output is correct
36	Correct	2 ms	748 KB	Output is correct
37	Correct	2 ms	748 KB	Output is correct
38	Correct	2 ms	748 KB	Output is correct
39	Correct	2 ms	748 KB	Output is correct
40	Correct	2 ms	748 KB	Output is correct
41	Correct	2 ms	748 KB	Output is correct
42	Correct	2 ms	748 KB	Output is correct
43	Correct	2 ms	748 KB	Output is correct
44	Correct	2 ms	748 KB	Output is correct
45	Correct	2 ms	748 KB	Output is correct
46	Correct	2 ms	748 KB	Output is correct
47	Correct	2 ms	748 KB	Output is correct
48	Correct	706 ms	172612 KB	Output is correct
49	Correct	694 ms	172720 KB	Output is correct
50	Correct	715 ms	172592 KB	Output is correct
51	Correct	700 ms	172592 KB	Output is correct
52	Correct	710 ms	172592 KB	Output is correct
53	Correct	704 ms	172592 KB	Output is correct
54	Correct	694 ms	172900 KB	Output is correct
55	Correct	706 ms	172720 KB	Output is correct
56	Correct	701 ms	172720 KB	Output is correct
57	Correct	696 ms	172848 KB	Output is correct
58	Correct	704 ms	172720 KB	Output is correct
59	Correct	691 ms	172720 KB	Output is correct
60	Correct	695 ms	172720 KB	Output is correct
61	Correct	704 ms	172592 KB	Output is correct
62	Correct	699 ms	172644 KB	Output is correct
63	Correct	704 ms	172764 KB	Output is correct
64	Correct	694 ms	172592 KB	Output is correct
65	Correct	698 ms	172592 KB	Output is correct
66	Correct	696 ms	172592 KB	Output is correct
67	Correct	710 ms	172772 KB	Output is correct
68	Correct	700 ms	172592 KB	Output is correct
69	Correct	696 ms	172772 KB	Output is correct
70	Correct	699 ms	172720 KB	Output is correct
71	Correct	705 ms	172720 KB	Output is correct
72	Correct	707 ms	172976 KB	Output is correct
73	Correct	716 ms	172644 KB	Output is correct
74	Correct	695 ms	172720 KB	Output is correct
75	Correct	699 ms	172796 KB	Output is correct
76	Correct	698 ms	172720 KB	Output is correct
77	Correct	703 ms	172720 KB	Output is correct
78	Correct	703 ms	172848 KB	Output is correct
79	Correct	693 ms	172720 KB	Output is correct
80	Correct	712 ms	172484 KB	Output is correct
81	Correct	720 ms	172592 KB	Output is correct
82	Correct	699 ms	172720 KB	Output is correct
83	Correct	698 ms	172852 KB	Output is correct
84	Correct	704 ms	172592 KB	Output is correct
85	Correct	699 ms	172592 KB	Output is correct
86	Correct	694 ms	172592 KB	Output is correct
87	Correct	694 ms	172556 KB	Output is correct
88	Correct	703 ms	172484 KB	Output is correct
89	Correct	698 ms	172672 KB	Output is correct
90	Correct	705 ms	172720 KB	Output is correct
91	Correct	699 ms	172848 KB	Output is correct
92	Correct	708 ms	172720 KB	Output is correct
93	Correct	705 ms	172836 KB	Output is correct
94	Correct	695 ms	172720 KB	Output is correct
95	Correct	690 ms	172720 KB	Output is correct
96	Correct	697 ms	172720 KB	Output is correct
97	Correct	701 ms	172980 KB	Output is correct
98	Correct	697 ms	172848 KB	Output is correct
99	Correct	706 ms	172992 KB	Output is correct
100	Correct	321 ms	86652 KB	Output is correct
101	Correct	323 ms	86884 KB	Output is correct
102	Correct	324 ms	86500 KB	Output is correct
103	Correct	325 ms	86628 KB	Output is correct
104	Correct	323 ms	86756 KB	Output is correct
105	Correct	448 ms	124260 KB	Output is correct
106	Correct	449 ms	124260 KB	Output is correct
107	Correct	452 ms	124388 KB	Output is correct
108	Correct	452 ms	124284 KB	Output is correct
109	Correct	448 ms	124248 KB	Output is correct
110	Correct	576 ms	125540 KB	Output is correct
111	Correct	576 ms	125296 KB	Output is correct
112	Correct	581 ms	125204 KB	Output is correct
113	Correct	583 ms	125284 KB	Output is correct
114	Correct	590 ms	125284 KB	Output is correct
115	Correct	579 ms	125296 KB	Output is correct
116	Correct	582 ms	125412 KB	Output is correct
117	Correct	581 ms	125284 KB	Output is correct
118	Correct	582 ms	125140 KB	Output is correct
119	Correct	583 ms	125412 KB	Output is correct
120	Correct	1 ms	364 KB	Output is correct
121	Correct	1 ms	364 KB	Output is correct
122	Correct	694 ms	160176 KB	Output is correct
123	Correct	696 ms	160200 KB	Output is correct
124	Correct	688 ms	160304 KB	Output is correct
125	Correct	694 ms	164912 KB	Output is correct
126	Correct	704 ms	164912 KB	Output is correct
127	Correct	693 ms	165040 KB	Output is correct
128	Correct	700 ms	165044 KB	Output is correct
129	Correct	701 ms	164912 KB	Output is correct
130	Correct	699 ms	165136 KB	Output is correct
131	Correct	699 ms	171440 KB	Output is correct
132	Correct	709 ms	171312 KB	Output is correct
133	Correct	689 ms	171312 KB	Output is correct