#715972 (C++17) No.1739 Princess vs. Dragoness (& AoE)

提出ソース

結果

問題	No.1739 Princess vs. Dragoness (& AoE)
ユーザー	bayashi-cl
提出日時	2021-11-12 23:06:04
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	10,523 bytes
コンパイル時間	1,487 ms
コンパイル使用メモリ	135,776 KB
実行使用メモリ	12,528 KB
最終ジャッジ日時	2024-05-04 10:46:45
合計ジャッジ時間	15,302 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	WA	-
testcase_03	AC	45 ms 6,944 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	530 ms 11,640 KB
testcase_07	AC	47 ms 6,944 KB
testcase_08	AC	393 ms 6,940 KB
testcase_09	AC	609 ms 8,576 KB
testcase_10	WA	-
testcase_11	AC	202 ms 6,940 KB
testcase_12	AC	45 ms 6,944 KB
testcase_13	AC	332 ms 7,636 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	324 ms 6,944 KB
testcase_20	AC	133 ms 6,940 KB
testcase_21	AC	552 ms 8,804 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	541 ms 11,256 KB
testcase_27	WA	-
testcase_28	AC	549 ms 11,248 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	545 ms 11,216 KB
testcase_32	AC	545 ms 11,256 KB
testcase_33	WA	-
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,944 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	3 ms 6,944 KB
testcase_39	AC	5 ms 6,944 KB
testcase_40	WA	-
testcase_41	AC	3 ms 6,944 KB
testcase_42	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード