Submission #1264225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264225		greenpizza12	Stove (JOI18_stove)	C++20	100 / 100	14 ms	1476 KiB

stove

#include <bits/stdc++.h>

// konakarthik12
// cpp20

namespace wrapped_std {

using std::begin;
using std::bit_width;
using std::cerr;
using std::cin;
using std::cout;
using std::declval;
using std::end;
using std::exit;
using std::fixed;
using std::gcd;
using std::lcm;
using std::greater;
using std::index_sequence;
using std::index_sequence_for;
using std::initializer_list;
using std::invoke;
using std::ios_base;
using std::istream;
using std::less;
using std::max;
using std::min;
using std::movable;
using std::mt19937;
using std::nullopt;
using std::optional;
using std::ostream;
using std::plus;
using std::minus;
using std::multiplies;
using std::random_access_iterator_tag;
using std::input_iterator;
using std::same_as;
using std::setprecision;
using std::size;
using std::stringstream;
using std::swap;
using std::tie;
using std::variant;
using std::integral;
using std::forward;
using std::bit_or;
using std::not_fn;
using std::function;
using std::iterator;
using std::span;
using std::adjacent_difference;
using std::strong_ordering;

using std::common_type_t;
using std::conditional_t;
using std::invoke_result_t;
using std::is_integral_v;
using std::is_signed_v;
using std::is_unsigned_v;
using std::make_unsigned_t;
using std::remove_reference_t;
using std::is_void_v;

using std::invocable;

using std::array;
using std::map;
using std::pair;
using std::predicate;
using std::tuple;
using std::string;

// using std::ranges::views::zip;
}

namespace ranges = std::ranges;
namespace chrono = std::chrono;
namespace views = std::views;

using namespace wrapped_std;

#define cexp constexpr

template <typename T>
struct NotBool {
  using type = T;
};

template <typename T>
using NotBool_t = NotBool<T>::type;

template <typename T>
concept HasValueType = requires { typename T::value_type; };

template <typename T>
concept HasIter = requires(T& container) {
  { container.begin() } -> same_as<decltype(container.end())>;
  { container.end() } -> same_as<decltype(container.begin())>;
};
template <typename T>
concept Printable = requires(ostream& os, const T& val) {
  { os << val } -> same_as<ostream&>;
};

template <typename T>
concept Readable = requires(istream& is, T& val) {
  { is >> val } -> same_as<istream&>;
};

template <typename T1>
concept Readable1D = requires(istream& is, const T1&) {
  { Readable<typename remove_reference_t<T1>::value_type> };
};

template <typename T1>
concept Readable2D = requires(istream& is, const T1&) {
  { Readable<typename remove_reference_t<T1>::value_type::value_type> };
  // not strings
  requires !same_as<typename remove_reference_t<T1>::value_type, std::string>;
};

template <typename T, typename Predicate>
concept SortPredicate = requires(T t1, T t2, Predicate p) {
  { p(t1, t2) } -> same_as<bool>;
};

template <typename T, template <class, class...> class C, const int offset = 0>
struct Con {
  using V = C<T>;
  using value_type = T;
  V v;

  Con() {
  }
  
  auto begin() {
    return this->v.begin();
  }

  auto end() {
    return this->v.end();
  }

  T& back() {
    return this->v.back();
  }

  int sz() const {
    return this->v.size();
  }

  void reserve(int size) {
    this->v.reserve(size);
  }

  void pb(const T& element) {
    this->v.push_back(element);
  }

  T rb() {
    T x = this->back();
    this->v.pop_back();
    return x;
  }

  void clear() {
    this->v.clear();
  }

  template <typename Comp = less<T>>
    requires SortPredicate<T, Comp>
  void sort(Comp comp = {}) {
    std::sort(this->v.begin(), this->v.end(), comp);
  }

  auto rsort() {
    return this->sort(greater());
  }
  
};

template <typename V, const int offset = 0>
struct vec : Con<NotBool_t<V>, std::vector, offset> {
  
  using Con<NotBool_t<V>, std::vector, offset>::Con;
};

template <typename V>
struct wec : vec<V, 1> {
  
  using vec<V, 1>::vec;
};

// template <size_t N, bool easy_index = false>
// class bitseta : public std::bitset<N> {
//  public:
//   using std::bitset<N>::bitset;

//   explicit operator int() const {
//     return (int) this->to_ullong();
//   }
//   explicit operator long long() const {
//     return (long long) this->to_ullong();
//   }

//   auto operator[](size_t index) {
//     if cexp (easy_index) index--;
//     return std::bitset<N>::operator[](index);
//   }

//   auto operator[](size_t index) const {
//     if cexp (easy_index) index--;
//     return std::bitset<N>::operator[](index);
//   }
//   bool operator<(const bitseta& other) const {
//     return this->to_ullong() < other.to_ullong();
//   }
//   bitseta operator^(const bitseta& other) const {
//     return std::bitset<N>::operator^(other);
//   }
// };

// template <int N>
// using witseta = bitseta<N, true>;

using ll = long long;

using wi = wec<int>;

// template <typename T>
//   requires integral<T>
// struct widen_pre_t {
//   using type = long long;
// };

template <typename T>
void reserve(T& v, size_t s) {
  cexp bool HasReserve = requires {
    { v.reserve(s) };
  };

  if cexp (HasReserve) {
    v.reserve(s);
  }
}

template <typename T>
  requires Readable<T>
void __read(T& arr) {
  cin >> arr;
}

template <typename V>
void append(V& v, const typename V::value_type& x) {
  cexp bool HasPB = requires {
    { v.pb(x) };
  };
  cexp bool HasPushBack = requires {
    { v.push_back(x) };
  };

  if cexp (HasPB) {
    v.pb(x);
  } else if cexp (HasPushBack) {
    v.push_back(x);
  } else {
    v.insert(x);
  }
}

template <typename Container>
  requires HasValueType<Container>
void __read1D(Container& v, const int& n) {
  using T = Container::value_type;
  v.clear();
  reserve(v, n);
  for (int i = 0; i < n; i++) {
    T x;
    __read(x);
    append(v, x);
  }
}

void read() {
}

template <typename T>
void read(T&& arg) {
  __read(std::forward<T>(arg));
}

template <typename T, typename T2, typename... Args>
  requires(Readable1D<T> && !Readable2D<T> && !Readable<T>)
void read(T&& first, T2&& second, Args&&... args) {
  __read1D(std::forward<T>(first), std::forward<T2>(second));
  read(std::forward<Args>(args)...);
}

template <typename T, typename... Args>
  requires(Readable<T> || (!Readable1D<T> && !Readable2D<T>) )
void read(T&& first, Args&&... args) {
  __read(std::forward<T>(first));
  read(std::forward<Args>(args)...);
}

#if defined(__clang__) or __cplusplus < 202302L
template <typename V>
  requires HasIter<V>
struct custom_adjacent_pairwise_view : public ranges::view_base {

  V& data;

  custom_adjacent_pairwise_view(V& input_data) : data(input_data) {
  }
  
  class custom_iterator {
   private:
    using base_iterator = decltype(begin(declval<V&>()));
    base_iterator iter;
    //    custom_iterator base_ = custom_adjacent_pairwise_view(data);

   public:
    using T = decltype(*iter);
    
    custom_iterator(base_iterator it) : iter(it) {
    }
    custom_iterator(custom_iterator const& other) : iter(other.iter) {
    }

    custom_iterator& operator++() {

      ++iter;
      return *this;
    }
    
    pair<T, T> operator*() const {
      return {*iter, *next(iter)};
    }

    bool operator==(const custom_iterator& other) const {
      return iter == other.iter;
    }
    
  };

  custom_iterator begin() {

    return custom_iterator(data.begin());
  }
  //
  custom_iterator end() {
    auto hmm = custom_iterator(std::prev(data.end()));
    return hmm;
  }
  
};

struct pairwise_tag {};
inline cexp pairwise_tag pairwise{};

template <typename T>
  requires HasIter<T>
auto operator|(T&& data, pairwise_tag) {
  return custom_adjacent_pairwise_view<T>(data);
}
#else
auto pairwise = views::pairwise;
#endif

template <typename T>
  requires Printable<T>
void __print(T x) {
  cout << x;
}

template <typename Arg, typename... Args>
void print(Arg&& arg, Args&&... args) {
  __print(arg);
  if cexp (sizeof...(args) > 0) {
    __print(' ');
    print(args...);
  }
}

template <typename... Args>
void println(Args&&... args) {
  print(args...);
  print('\n');
}

template <typename Res>
void handle_print(Res& res) {
  println(res);
}

template <typename Func>
  requires requires(Func func) {
    { invoke_result_t<Func>() } -> movable;
  }
void call_print(Func func) {
  auto result = invoke(func);
  handle_print(result);
}

template <typename Func>
  requires requires(Func func) {
    { invoke_result_t<Func>() };
  }
void handle_solve(Func func) {
  call_print(func);
}

void init_main() {
  cin.tie(0)->sync_with_stdio(0);

  cout << fixed << setprecision(15);
}

template <typename T = void>
void init() {
}

// ********************************************** ACTUAL CODE STARTS HERE **********************************************

ll solve() {
  int n, k;
  read(n, k);

  wi arr;
  read(arr, n);

  wi gaps;
  for (auto [a, b]: arr | pairwise) {
    int gap = b - a - 1;
    gaps.pb(gap);
  }
  gaps.rsort();
  ll ans = 0;
  while (gaps.sz() > k - 1) ans += gaps.rb();
  return n + ans;
}

// **********************************************  ACTUAL CODE ENDS HERE  **********************************************

int main() {
  init_main();

  init();
  handle_solve(solve);

  return 0;
}

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