#904267 (C++23) No.409 ダイエット

提出ソース

結果

問題	No.409 ダイエット
ユーザー	Pachicobue
提出日時	2023-08-16 03:40:55
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	13,055 bytes
コンパイル時間	4,334 ms
コンパイル使用メモリ	267,388 KB
実行使用メモリ	15,252 KB
最終ジャッジ日時	2024-05-03 13:11:56
合計ジャッジ時間	8,691 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	WA	-
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	WA	-
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	WA	-
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	WA	-
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	WA	-
testcase_22	AC	1 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	WA	-
testcase_34	AC	2 ms 5,376 KB
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	AC	32 ms 11,496 KB
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;
using f128 = __float128;
constexpr i32 operator"" _i32(u64 v) { return v; }
constexpr u32 operator"" _u32(u64 v) { return v; }
constexpr i64 operator"" _i64(u64 v) { return v; }
constexpr u64 operator"" _u64(u64 v) { return v; }
constexpr f64 operator"" _f64(f80 v) { return v; }
constexpr f80 operator"" _f80(f80 v) { return v; }
using Istream = std::istream;
using Ostream = std::ostream;
using Str = std::string;
template<typename T> using Lt = std::less<T>;
template<typename T> using Gt = std::greater<T>;
template<int n> using BSet = std::bitset<n>;
template<typename T1, typename T2> using Pair = std::pair<T1, T2>;
template<typename... Ts> using Tup = std::tuple<Ts...>;
template<typename T, int N> using Arr = std::array<T, N>;
template<typename... Ts> using Deq = std::deque<Ts...>;
template<typename... Ts> using Set = std::set<Ts...>;
template<typename... Ts> using MSet = std::multiset<Ts...>;
template<typename... Ts> using USet = std::unordered_set<Ts...>;
template<typename... Ts> using UMSet = std::unordered_multiset<Ts...>;
template<typename... Ts> using Map = std::map<Ts...>;
template<typename... Ts> using MMap = std::multimap<Ts...>;
template<typename... Ts> using UMap = std::unordered_map<Ts...>;
template<typename... Ts> using UMMap = std::unordered_multimap<Ts...>;
template<typename... Ts> using Vec = std::vector<Ts...>;
template<typename... Ts> using Stack = std::stack<Ts...>;
template<typename... Ts> using Queue = std::queue<Ts...>;
template<typename T> using MaxHeap = std::priority_queue<T>;
template<typename T> using MinHeap = std::priority_queue<T, Vec<T>, Gt<T>>;
template<typename T> using Opt = std::optional<T>;
template<typename... Ts> using Span = std::span<Ts...>;
constexpr bool LOCAL = false;
template<typename T> static constexpr T OjLocal(T oj, T local) { return LOCAL ? local : oj; }
template<typename T> constexpr T LIMMIN = std::numeric_limits<T>::min();
template<typename T> constexpr T LIMMAX = std::numeric_limits<T>::max();
template<typename T> constexpr T INF = (LIMMAX<T> - 1) / 2;
template<typename T = i64> constexpr T TEN(int N) { return N == 0 ? T{1} : TEN<T>(N - 1) * T{10}; }
constexpr auto ABS(auto x) { return (x >= 0 ? x : -x); }
constexpr auto makePair(const auto& x1, const auto& x2) { return std::make_pair(x1, x2); }
constexpr auto makeTup(const auto&... xs) { return std::make_tuple(xs...); }
template<typename T> constexpr bool chmin(T& x, const T& y, auto comp) { return (comp(y, x) ? (x = y, true) : false); }
template<typename T> constexpr bool chmin(T& x, const T& y) { return chmin(x, y, Lt<T>{}); }
template<typename T> constexpr bool chmax(T& x, const T& y, auto comp) { return (comp(x, y) ? (x = y, true) : false); }
template<typename T> constexpr bool chmax(T& x, const T& y) { return chmax(x, y, Lt<T>{}); }
constexpr i64 floorDiv(i64 x, i64 y)
{
    assert(y != 0);
    if (y < 0) { x = -x, y = -y; }
    return x >= 0 ? x / y : (x - y + 1) / y;
}
constexpr i64 ceilDiv(i64 x, i64 y)
{
    assert(y != 0);
    if (y < 0) { x = -x, y = -y; }
    return x >= 0 ? (x + y - 1) / y : x / y;
}
template<typename T> constexpr T powerSemiGroup(const T& x, i64 N, auto mul)
{
    assert(N > 0);
    if (N == 1) { return x; }
    return (N % 2 == 1 ? mul(x, powerSemiGroup(x, N - 1, mul)) : powerSemiGroup(mul(x, x), N / 2, mul));
}
template<typename T> constexpr auto powerSemiGroup(const auto& v, i64 N) { return powerSemiGroup(v, N, std::multiplies<T>{}); }
template<typename T> constexpr T powerMonoid(const T& x, i64 N, const T& e, auto mul)
{
    assert(N >= 0);
    return (N == 0 ? e : powerSemiGroup(x, N, mul));
}
template<typename T> constexpr T powerMonoid(T x, i64 N, const T& e) { return powerMonoid(x, N, e, std::multiplies<T>{}); }
template<typename T> constexpr T powerInt(T x, i64 N) { return powerMonoid(x, N, T{1}); }
constexpr u64 powerMod(u64 x, i64 N, u64 mod)
{
    assert(0 < mod);
    return powerMonoid(x, N, u64{1}, [&](u64 x, u64 y) {
        if (mod <= (u64)LIMMAX<u32>) {
            return x * y % mod;
        } else {
            return (u64)((u128)x * y % mod);
        }
    });
}
constexpr auto sumAll(const auto& xs) { return std::accumulate(std::begin(xs), std::end(xs), decltype(xs[0]){}); }
constexpr int lbInd(const auto& xs, const auto& x) { return std::ranges::lower_bound(xs, x) - std::begin(xs); }
constexpr int ubInd(const auto& xs, const auto& x) { return std::ranges::upper_bound(xs, x) - std::begin(xs); }
constexpr int find(const auto& xs, const auto& x)
{
    const int i = lbInd(xs, x);
    if (i < std::ssize(xs) and xs[i] == x) { return i; }
    return std::ssize(xs);
}
constexpr void concat(auto& xs1, const auto& xs2) { std::ranges::copy(xs2, std::back_inserter(xs1)); }
constexpr auto concatCopy(const auto& xs1, const auto& xs2)
{
    auto Ans = xs1;
    return concat(Ans, xs2), Ans;
}
template<typename Ts, typename T> constexpr void fillAll(Ts& arr, const T& x)
{
    if constexpr (std::is_convertible<T, Ts>::value) {
        arr = x;
    } else {
        for (auto& subarr : arr) { fillAll(subarr, x); }
    }
}
template<typename T> constexpr Vec<T> genVec(int N, auto gen)
{
    Vec<T> ans;
    std::ranges::generate_n(std::back_inserter(ans), N, gen);
    return ans;
}
constexpr auto minAll(const auto& xs, auto... args) { return std::ranges::min(xs, args...); }
constexpr auto maxAll(const auto& xs, auto... args) { return std::ranges::max(xs, args...); }
constexpr int minInd(const auto& xs, auto... args) { return std::ranges::min_element(xs, args...) - std::begin(xs); }
constexpr int maxInd(const auto& xs, auto... args) { return std::ranges::max_element(xs, args...) - std::begin(xs); }
template<typename T = int> constexpr Vec<T> iotaVec(int N, T offset = 0)
{
    Vec<T> ans(N);
    std::iota(std::begin(ans), std::end(ans), offset);
    return ans;
}
constexpr void plusAll(auto& xs, const auto& x)
{
    std::ranges::for_each(xs, [&](auto& e) { e += x; });
}
constexpr void reverseAll(auto& xs) { std::ranges::reverse(xs); }
constexpr void sortAll(auto& xs, auto... args) { std::ranges::sort(xs, args...); }
constexpr auto runLengthEncode(const auto& xs)
{
    using T = typename std::decay<decltype(xs[0])>::type;
    Vec<Pair<T, int>> Ans;
    auto [l, px] = makePair(0, T{});
    for (const T& x : xs) {
        if (l == 0 or x != px) {
            if (l > 0) { Ans.push_back({px, l}); }
            l = 1, px = x;
        } else {
            l++;
        }
    }
    if (l > 0) { Ans.push_back({px, l}); }
    return Ans;
}
inline Ostream& operator<<(Ostream& os, u128 v)
{
    Str ans;
    if (v == 0) { ans = "0"; }
    while (v) { ans.push_back('0' + v % 10), v /= 10; }
    std::reverse(ans.begin(), ans.end());
    return os << ans;
}
inline Ostream& operator<<(Ostream& os, i128 v)
{
    bool minus = false;
    if (v < 0) { minus = true, v = -v; }
    return os << (minus ? "-" : "") << (u128)v;
}
constexpr bool isBitOn(u64 x, int i) { return assert(0 <= i and i < 64), ((x >> i) & 1_u64); }
constexpr bool isBitOff(u64 x, int i) { return assert(0 <= i and i < 64), (not isBitOn(x, i)); }
constexpr u64 bitMask(int w) { return assert(0 <= w and w <= 64), (w == 64 ? ~0_u64 : (1_u64 << w) - 1); }
constexpr u64 bitMask(int s, int e) { return assert(0 <= s and s <= e and e <= 64), (bitMask(e - s) << s); }
constexpr int floorLog2(u64 x) { return 63 - std::countl_zero(x); }
constexpr int ceilLog2(u64 x) { return x == 0 ? -1 : std::bit_width(x - 1); }
constexpr int order2(u64 x) { return std::countr_zero(x); }
template<typename F> struct Fix : F
{
    constexpr Fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> constexpr auto operator()(Args&&... args) const
    {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};
class irange
{
private:
    struct itr
    {
        constexpr itr(i64 start, i64 end, i64 step) : m_cnt{start}, m_step{step}, m_end{end} {}
        constexpr bool operator!=(const itr&) const { return (m_step > 0 ? m_cnt < m_end : m_end < m_cnt); }
        constexpr i64 operator*() { return m_cnt; }
        constexpr itr& operator++() { return m_cnt += m_step, *this; }
        i64 m_cnt, m_step, m_end;
    };
    i64 m_start, m_end, m_step;
public:
    constexpr irange(i64 start, i64 end, i64 step = 1) : m_start{start}, m_end{end}, m_step{step} { assert(step != 0); }
    constexpr itr begin() const { return itr{m_start, m_end, m_step}; }
    constexpr itr end() const { return itr{m_start, m_end, m_step}; }
};
constexpr irange rep(i64 end) { return irange(0, end, 1); }
constexpr irange per(i64 rend) { return irange(rend - 1, -1, -1); }
template<typename T> class MonotoneCHT
{
    using L = Pair<T, T>;
    static constexpr auto Null = std::nullopt;
    static bool popAble(const L& l1, const L& l2, const L& l3)
    {
        const auto& [a1, b1] = l1;
        const auto& [a2, b2] = l2;
        const auto& [a3, b3] = l3;
        assert(a1 > a2 and a2 > a3);
        if constexpr (std::is_integral_v<T>) {
            return floorDiv(b2 - b1, a1 - a2) >= floorDiv(b3 - b1, a1 - a3);
        } else {
            return (a1 - a3) * (b2 - b1) >= (a1 - a2) * (b3 - b1);
        }
    }
    static bool comp(const L& l1, const L& l2, Opt<T> x)
    {
        const auto& [a1, b1] = l1;
        const auto& [a2, b2] = l2;
        if (a1 == a2) { return b1 < b2; }
        if (x == Null) { return a1 < a2; }
        if constexpr (std::is_integral_v<T>) {
            if (a1 > a2) {
                return x.value() <= floorDiv(b2 - b1, a1 - a2);
            } else {
                return floorDiv(b1 - b2, a2 - a1) < x.value();
            }
        } else {
            return a1 * x.value() + b1 < a2 * x.value() + b2;
        }
    }
public:
    MonotoneCHT() : m_prev_x{Null} {}
    void addLine(const L& l)
    {
        if (m_lines.empty()) { return m_lines.push_back(l), void(); }
        if (m_lines.back().first == l.first and m_lines.back().second <= l.second) { return; }
        while ((int)m_lines.size() >= 2) {
            if (not popAble(m_lines[m_lines.size() - 2], m_lines[m_lines.size() - 1], l)) { break; }
            m_lines.pop_back();
        }
        m_lines.push_back(l);
    }
    Opt<L> minLine(T x)
    {
        if (m_lines.empty()) { return Null; }
        assert(m_prev_x == Null or m_prev_x.value() <= x);
        m_prev_x = x;
        while (m_lines.size() >= 2) {
            if (comp(m_lines[0], m_lines[1], x)) { break; }
            m_lines.pop_front();
        }
        return m_lines.front();
    }
private:
    Opt<T> m_prev_x;
    Deq<L> m_lines;
};
class Printer
{
public:
    Printer(Ostream& os = std::cout) : m_os{os} { m_os << std::fixed << std::setprecision(15); }
    int operator()(const auto&... args) { return dump(args...), 0; }
    int ln(const auto&... args) { return dump(args...), m_os << '\n', 0; }
    int el(const auto&... args) { return dump(args...), m_os << std::endl, 0; }
private:
    void dump(const auto& v) { m_os << v; }
    int dump(const auto& v, const auto&... args) { return dump(v), m_os << ' ', dump(args...), 0; }
    template<typename... Args> void dump(const Vec<Args...>& vs)
    {
        for (Str delim = ""; const auto& v : vs) { m_os << std::exchange(delim, " "), dump(v); }
    }
    Ostream& m_os;
};
inline Printer out;
class Scanner
{
public:
    Scanner(Istream& is = std::cin) : m_is{is} { m_is.tie(nullptr)->sync_with_stdio(false); }
    template<typename T> T val()
    {
        T v;
        return m_is >> v, v;
    }
    template<typename T> T val(T offset) { return val<T>() - offset; }
    template<typename T> Vec<T> vec(int N)
    {
        return genVec<T>(N, [&]() { return val<T>(); });
    }
    template<typename T> Vec<T> vec(int N, T offset)
    {
        return genVec<T>(N, [&]() { return val<T>(offset); });
    }
    template<typename T> Vec<Vec<T>> vvec(int n, int m)
    {
        return genVec<Vec<T>>(n, [&]() { return vec<T>(m); });
    }
    template<typename T> Vec<Vec<T>> vvec(int n, int m, const T offset)
    {
        return genVec<Vec<T>>(n, [&]() { return vec<T>(m, offset); });
    }
    template<typename... Args> auto tup() { return Tup<Args...>{val<Args>()...}; }
    template<typename... Args> auto tup(Args... offsets) { return Tup<Args...>{val<Args>(offsets)...}; }
private:
    Istream& m_is;
};
inline Scanner in;
int main()
{
    const auto [N, A, B, W] = in.tup<int, i64, i64, i64>();
    auto ds = Vec<i64>{0};
    concat(ds, in.vec<i64>(N));
    ds.push_back(0);
    Vec<i64> dp(N + 2, INF<i64>);
    dp[0] = 0;
    MonotoneCHT<i64> cht;
    for (int i : rep(N + 2)) {
        if (i != 0) {
            const auto [a, b] = cht.minLine(i).value();
            dp[i] = ds[i] * 2 - A * (i - 1) * 2 + B * i * i + (a * i + b);
        }
        cht.addLine({-B * (2 * i + 1), dp[i] + A * 2 * i + B * (i + 1) * i});
    }
    out.ln(W + dp.back() / 2);
    return 0;
}

yukicoder

結果

テストケース

ソースコード