結果
問題 | No.1739 Princess vs. Dragoness (& AoE) |
ユーザー |
|
提出日時 | 2021-11-12 23:06:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,523 bytes |
コンパイル時間 | 1,281 ms |
コンパイル使用メモリ | 128,980 KB |
最終ジャッジ日時 | 2025-01-25 17:27:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 23 WA * 17 |
ソースコード
#line 2 "byslib/template/bys.hpp"#ifndef LOCAL#define NDEBUG#endif#include <algorithm>#include <array>#include <cassert>#include <cmath>#include <complex>#include <iomanip>#include <iostream>#include <iterator>#include <limits>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <vector>namespace bys {using std::array, std::vector, std::string, std::set, std::map, std::pair;using std::cin, std::cout, std::endl;using std::min, std::max, std::sort, std::reverse, std::abs, std::pow;// aliasusing ll = long long int;using ld = long double;using Pa = pair<int, int>;using Vec = vector<int>;using VecVec = std::vector<Vec>;template <class T>using uset = std::unordered_set<T>;template <class S, class T>using umap = std::unordered_map<S, T>;// constconstexpr int MOD = 998244353;constexpr int INF = std::numeric_limits<int>::max() / 2;constexpr ll LINF = std::numeric_limits<ll>::max() / 2;// I/O// pairtemplate <class T, class U>std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {return is >> p.first >> p.second;}template <typename T, typename U>std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {return os << p.first << " " << p.second;}// STL containerstruct is_container_impl {template <typename T>static auto check(T&& obj)-> decltype(obj.begin(), obj.end(), std::true_type{});template <typename T>static auto check(...) -> std::false_type;};template <typename T>class is_container: public decltype(is_container_impl::check<T>(std::declval<T>())) {};template <typename C,typename std::enable_if<is_container<C>::value &&!std::is_same<C, std::string>::value &&!std::is_same<C, std::wstring>::value,std::nullptr_t>::type = nullptr>std::ostream& operator<<(std::ostream& os, const C& container) noexcept {std::for_each(std::begin(container), std::prev(std::end(container)),[&](auto e) { os << e << ' '; });return os << *std::prev(std::end(container));}template <typename C,typename std::enable_if<is_container<C>::value &&!std::is_same<C, std::string>::value &&!std::is_same<C, std::wstring>::value,std::nullptr_t>::type = nullptr>std::istream& operator>>(std::istream& is, C& container) {std::for_each(std::begin(container), std::end(container),[&](auto&& e) { is >> e; });return is;}// I/O helpertemplate <class T>inline T input() {T n;cin >> n;return n;}template <class T>inline vector<T> input(int n) {vector<T> res(n);cin >> res;return res;}template <class T, size_t N>inline std::array<T, N> input() {std::array<T, N> res;cin >> res;return res;}template <class S, class T, class... Us>std::tuple<S, T, Us...> input() {std::tuple<S, T, Us...> res;std::apply([](auto&... e) { (cin >> ... >> e); }, res);return res;}struct Print {std::ostream& os;char sep = ' ', end = '\n';Print() : os(std::cout) {}Print(std::ostream& os) : os(os) {}~Print() { os << std::flush; }void operator()() { os << end; }template <class T>void operator()(const T& a) {os << a << end;}template <class T, class... Ts>void operator()(const T& a, const Ts&... b) {os << a;(os << ... << (os << sep, b));os << end;}} print, debug(std::cerr);// utilitytemplate <class T>inline bool chmax(T& a, const T& b) {if (a < b) {a = b;return 1;}return 0;}template <class T>inline bool chmin(T& a, const T& b) {if (b < a) {a = b;return 1;}return 0;}template <class T>inline T iceil(T a, T b) {return (a + b - 1) / b;}inline bool pop(int s, int d) { return s & (1 << d); }// configinline void init() {cin.tie(nullptr);std::ios::sync_with_stdio(false);cout << std::fixed << std::setprecision(11);std::cerr << std::boolalpha;}// macro#ifdef LOCAL#define DEBUG(...) debug("[debug] line:", __LINE__, "\n", __VA_ARGS__)#else#define DEBUG(...)#endif// clang-format off#define EXIT(...) { print(__VA_ARGS__); return; }// clang-format on// solvervoid solve();void solver(int t = 1) {for (int i = 0; i < t; ++i) solve();}} // namespace bys#line 3 "byslib/util.hpp"namespace bys {template <class T, std::size_t I>struct ItemGetter {bool operator()(const T& lh, const T& rh) { return lh[I] < rh[I]; }};/*** @brief 二分探索法* https://atcoder.jp/contests/abc205/submissions/23500985* @tparam T 初期値と返り値、is_okの第一引数 int or long long intを想定* @param ok (T): is_okを満たす初期値* @param ng (T): is_okを満たさない初期値* @param is_ok (bool()): 判定用ラムダ式* @param args... (Args...): is_okに渡される引数 可変長* @return (T): is_okを満たす最大/小の整数*/template <typename T, class Lambda, class... Args>T meguru_bisect(T ok, T ng, Lambda is_ok, Args... args) {assert(is_ok(ok, args...));assert(!is_ok(ng, args...));while (std::abs(ok - ng) > 1) {T mid = (ok + ng) / 2;if (is_ok(mid, args...)) {ok = mid;} else {ng = mid;}}return ok;}template <class Lambda, class... Args>double bisect_float(double ok, double ng, int rep, Lambda is_ok, Args... args) {assert(is_ok(ok, args...));assert(!is_ok(ng, args...));for (int i = 0; i < rep; i++) {double mid = (ok + ng) / 2;if (is_ok(mid, args...)) {ok = mid;} else {ng = mid;}}return ok;}template <class T>struct Compress {vector<T> cp;Compress() {}Compress(vector<T>& vec) : cp(vec) {}void add(T v) { cp.push_back(v); }void construct() {sort(std::begin(cp), std::end(cp));cp.erase(std::unique(std::begin(cp), std::end(cp)), cp.end());}int get(T v) {auto itr = std::lower_bound(std::begin(cp), std::end(cp), v);assert(*itr == v);return std::distance(cp.begin(), itr);}};template <class T>T cumulate(vector<T>& vec, T init = 0) {T sum = init;for (auto&& i : vec) {sum += i;i = sum;}return sum;}template <class T, class BinOp>T cumulate(vector<T>& vec, BinOp op, T init = 0) {T sum = init;for (auto&& i : vec) {sum = op(sum, i);i = sum;}return sum;}struct Board {int h, w;Board(int row, int col) : h(row), w(col) {}bool contain(int row, int col) {return 0 <= row && row < h && 0 <= col && col < w;}vector<pair<int, int>> next(int i, int j,const vector<pair<int, int>> delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {vector<pair<int, int>> res;for (auto [di, dj] : delta) {int ni = i + di;int nj = j + dj;if (contain(ni, nj)) res.push_back({ni, nj});}return res;}int index(int i, int j) { return i * w + j; }int area() { return h * w; }};template <class T>struct CumulativeSum {vector<T> data;CumulativeSum(int n) : data(n + 1){};CumulativeSum(const vector<T>& v) : data(v.size() + 1) {std::copy(v.begin(), v.end(), std::next(data.begin()));};void set(int i, int x) {assert(!build);data[i + 1] = x;}void construct() {assert(!build);std::partial_sum(data.begin(), data.end(), data.begin());build = true;}// [l, r)T sum(int l, int r) {assert(build);return data[r] - data[l];}private:bool build = false;};template <class T>struct CumulativeSum2D {vector<vector<T>> data;CumulativeSum2D(int n, int m) : data(n + 1, vector<T>(m + 1)){};CumulativeSum2D(const vector<vector<T>>& v): data(v.size() + 1, vector<T>(v[0].size() + 1)) {int n = v.size();for (int i = 0; i < n; ++i) {std::copy(v[i].begin(), v[i].end(), std::next(data[i + 1].begin()));}};void set(int i, int j, int x) {assert(!build);data[i + 1][j + 1] = x;}T get(int i, int j) const { return data[i + 1][j + 1]; }void construct() {assert(!build);int n = data.size();int m = data[0].size();for (int i = 1; i < n; ++i) {for (int j = 1; j < m; ++j) {data[i][j] +=data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];}}build = true;}// [si, gi), [sj, gj)T sum(int si, int sj, int gi, int gj) {assert(build);return (data[gi][gj] - data[si][gj] - data[gi][sj] + data[si][sj]);}private:bool build = false;};} // namespace bys#line 3 "e/e.cpp"namespace bys {void solve() {auto [n, a, b, x, y] = input<ll, 5>();auto h = input<ll>(n);using Data = pair<ll, int>;auto ok = [&](ll th) -> bool {if (th < 0) return false;ll rem_b = y * b;std::priority_queue<Data, vector<Data>, std::greater<Data>> que;for (int i = 0; i < n; ++i) que.push({h[i] - th, i});for (int i = 0; i < a; ++i) {auto top = que.top();top.first -= x;que.push(top);}vector<Data> h2;for (int i = 0; i < n; ++i) {h2.push_back(que.top());que.pop();}sort(h2.begin(), h2.end(),[](Data a, Data b) { return a.second < b.second; });for (auto& [hi, id] : h2) {if (hi > 0) {if (hi > rem_b) {return false;} else {rem_b -= hi;}}}return true;};ll ma = *std::max_element(h.begin(), h.end());print(meguru_bisect(ma, -1LL, ok));}} // namespace bysint main() {bys::init();bys::solver(/* bys::input<int>() */);return 0;}