Bundle
Copy
#line 1 "test/aoj_0613.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613"
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#include <cstddef>
#line 11 "utility/literals.cpp"
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
constexpr int8_t operator ""_i8(unsigned long long n) { return n; }
constexpr int16_t operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t operator ""_u8(unsigned long long n) { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }
#line 1 "DataStructure/foldable_queue.cpp"
/**
* @brief fold 可能キュー
* @author えびちゃん
*/
#line 10 "DataStructure/foldable_queue.cpp"
#include <stack>
#line 12 "DataStructure/foldable_queue.cpp"
template <class Monoid>
class foldable_queue {
public:
using size_type = size_t;
using value_type = Monoid;
private:
std::stack<value_type> M_front, M_back;
value_type M_back_folded{};
void M_rotate_to_front() {
if (!M_back.empty()) {
M_front.push(std::move(M_back.top()));
M_back.pop();
}
while (!M_back.empty()) {
M_back.top() += M_front.top();
M_front.push(std::move(M_back.top()));
M_back.pop();
}
M_back_folded = value_type{};
}
public:
size_type size() const { return M_front.size() + M_back.size(); }
bool empty() const noexcept { return M_front.empty() && M_back.empty(); }
void push(value_type const& x) {
M_back.push(x);
M_back_folded += M_back.top();
}
template <typename... Args>
void emplace(Args&&... args) {
M_back.emplace(std::forward<Args>(args)...);
M_back_folded += M_back.top();
}
void pop() {
if (M_front.empty()) M_rotate_to_front();
M_front.pop();
}
value_type fold() const {
if (M_front.empty()) return M_back_folded;
return M_front.top() + M_back_folded;
}
};
#line 1 "utility/monoid/max.cpp"
/**
* @brief max を得る演算のモノイド
* @author えびちゃん
*/
#line 11 "utility/monoid/max.cpp"
#line 1 "utility/limits.cpp"
/**
* @brief 型依存の定数
* @author えびちゃん
*/
#include <limits>
#line 11 "utility/limits.cpp"
template <typename Tp>
class limits: public std::numeric_limits<Tp> {};
template <typename T1, typename T2>
class limits<std::pair<T1, T2>> {
public:
static constexpr auto min() {
return std::make_pair(limits<T1>::min(), limits<T2>::min());
}
static constexpr auto max() {
return std::make_pair(limits<T1>::max(), limits<T2>::max());
}
};
#line 13 "utility/monoid/max.cpp"
template <typename Tp>
class max_monoid {
public:
using value_type = Tp;
private:
value_type M_x = limits<value_type>::min();
public:
max_monoid() = default; // identity
max_monoid(max_monoid const&) = default;
max_monoid(max_monoid&&) = default;
max_monoid(value_type const& x): M_x(x) {};
max_monoid(value_type&& x): M_x(std::move(x)) {};
max_monoid& operator =(max_monoid const&) = default;
max_monoid& operator =(max_monoid&&) = default;
max_monoid& operator +=(max_monoid const& that) {
M_x = std::max(M_x, that.M_x);
return *this;
}
max_monoid& operator +=(max_monoid&& that) {
M_x = std::max(M_x, std::move(that.M_x));
return *this;
}
max_monoid operator +(max_monoid const& that) const {
return max_monoid(*this) += that;
}
max_monoid operator +(max_monoid&& that) const {
return max_monoid(*this) += std::move(that);
}
value_type const& get() const { return M_x; }
};
#line 13 "test/aoj_0613.test.cpp"
int main() {
size_t n;
intmax_t d;
scanf("%zu %jd", &n, &d);
std::vector<std::pair<intmax_t, intmax_t>> xy(n);
for (auto& [xi, yi]: xy)
scanf("%jd %jd", &xi, &yi);
if (n < 3) xy.resize(3, {0, 0});
n = xy.size();
size_t n1 = (n+1)/2;
auto neko = [&](auto first, auto last) {
std::vector<std::pair<intmax_t, intmax_t>> z(first, last);
std::vector<std::pair<intmax_t, intmax_t>> res{{0, 0}};
for (size_t i = 0; i < (1_zu << z.size()); ++i) {
size_t j = i;
do {
intmax_t xi = 0, yi = 0;
for (size_t k = 0; k < z.size(); ++k) {
if (~i >> k & 1) continue;
if (j >> k & 1) {
xi += z[k].first;
yi += z[k].second;
} else {
xi -= z[k].first;
yi -= z[k].second;
}
}
res.emplace_back(xi, yi);
j = (j-1) & i;
} while (j != i);
}
return res;
};
auto xy1 = neko(xy.begin(), xy.begin()+n1);
auto xy2 = neko(xy.begin()+n1, xy.end());
std::sort(xy1.rbegin(), xy1.rend());
std::sort(xy2.begin(), xy2.end());
intmax_t const inf = 1e18;
intmax_t res = -inf;
foldable_queue<max_monoid<intmax_t>> y2;
size_t il = 0, ir = 0;
for (auto const& p: xy1) {
auto [x1, y1] = p;
while (ir < xy2.size() && xy2[ir].first+x1 <= d) {
y2.push(xy2[ir++].second);
}
while (il < ir && xy2[il].first+x1 < -d) {
++il;
y2.pop();
}
intmax_t cur = y2.fold().get();
if (cur < -inf) continue;
cur += y1;
res = std::max(res, cur);
}
if (res < -inf) return puts("-1"), 0;
printf("%jd\n", res);
}