結果

問題 No.1739 Princess vs. Dragoness (& AoE)
ユーザー bayashi-cl
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
// alias
using 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>;
// const
constexpr int MOD = 998244353;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr ll LINF = std::numeric_limits<ll>::max() / 2;
// I/O
// pair
template <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 container
struct 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 helper
template <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);
// utility
template <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); }
// config
inline 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
// solver
void 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 bys
int main() {
bys::init();
bys::solver(/* bys::input<int>() */);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0