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

• 問題: No.409 ダイエット
• ユーザー: kwm_t
• 提出日時: 2026-06-10 12:08:13
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 40 ms / 2,000 ms
• コード長: 4,457 bytes
• コンパイル時間: 2,478 ms
• コンパイル使用メモリ: 341,480 KB
• 実行使用メモリ: 11,008 KB
• 最終ジャッジ日時: 2026-06-10 12:08:21
• 合計ジャッジ時間: 7,582 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 92

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_DATA_STRUCTURE_CONVEX_HULL_TRICK_ADD_MONOTONE_HPP
#define KWM_T_DATA_STRUCTURE_CONVEX_HULL_TRICK_ADD_MONOTONE_HPP

#include <deque>
#include <utility>
#include <cassert>
#include <cmath>

namespace kwm_t::data_structure {

/**
 * @brief Convex Hull Trick (Add Monotone)
 *
 * 典型用途:
 *   - 直線集合に対する最小値 / 最大値クエリ
 *   - 傾きが単調に追加される場合のDP最適化
 *
 * 計算量:
 *   - add: amortized O(1)
 *   - query: O(log N)
 *   - monotone query: O(1)
 * verified
 *   https://atcoder.jp/contests/abc228/submissions/75110284
 *   https://atcoder.jp/contests/abc289/submissions/75110314
 */
template <typename T, bool isMin>
struct ConvexHullTrickAddMonotone {
	std::deque<std::pair<T, T>> H;

	ConvexHullTrickAddMonotone() = default;

	bool empty() const { return H.empty(); }
	void clear() { H.clear(); }

	inline int sgn(T x) { return x == 0 ? 0 : (x < 0 ? -1 : 1); }

	using D = long double;

	inline bool check(const std::pair<T, T> &a,
		const std::pair<T, T> &b,
		const std::pair<T, T> &c) {
		if (b.second == a.second || c.second == b.second)
			return sgn(b.first - a.first) * sgn(c.second - b.second) >=
			sgn(c.first - b.first) * sgn(b.second - a.second);

		return
			D(b.first - a.first) * sgn(c.second - b.second) / D(std::abs(b.second - a.second)) >=
			D(c.first - b.first) * sgn(b.second - a.second) / D(std::abs(c.second - b.second));
	}

	void add(T a, T b) {
		if (!isMin) a *= -1, b *= -1;
		std::pair<T, T> line(a, b);

		if (empty()) {
			H.emplace_front(line);
			return;
		}

		if (H.front().first <= a) {
			if (H.front().first == a) {
				if (H.front().second <= b) return;
				H.pop_front();
			}
			while (H.size() >= 2 && check(line, H.front(), H[1])) H.pop_front();
			H.emplace_front(line);
		}
		else {
			assert(a <= H.back().first);
			if (H.back().first == a) {
				if (H.back().second <= b) return;
				H.pop_back();
			}
			while (H.size() >= 2 && check(H[H.size() - 2], H.back(), line)) H.pop_back();
			H.emplace_back(line);
		}
	}

	inline T get_y(const std::pair<T, T> &a, const T &x) {
		return a.first * x + a.second;
	}

	T query(T x) {
		assert(!empty());
		int l = -1, r = (int)H.size() - 1;
		while (l + 1 < r) {
			int m = (l + r) >> 1;
			if (get_y(H[m], x) >= get_y(H[m + 1], x)) l = m;
			else r = m;
		}
		if (isMin) return get_y(H[r], x);
		return -get_y(H[r], x);
	}

	T query_monotone_inc(T x) {
		assert(!empty());
		while (H.size() >= 2 && get_y(H.front(), x) >= get_y(H[1], x))
			H.pop_front();
		if (isMin) return get_y(H.front(), x);
		return -get_y(H.front(), x);
	}

	T query_monotone_dec(T x) {
		assert(!empty());
		while (H.size() >= 2 &&
			get_y(H.back(), x) >= get_y(H[H.size() - 2], x))
			H.pop_back();
		if (isMin) return get_y(H.back(), x);
		return -get_y(H.back(), x);
	}
};

} // namespace kwm_t::data_structure

#endif // KWM_T_DATA_STRUCTURE_CONVEX_HULL_TRICK_ADD_MONOTONE_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, a, b, w; cin >> n >> a >> b >> w;
	vector<int>d(n);
	rep(i, n)cin >> d[i];
	vector<long long>dp(n + 1);
	kwm_t::data_structure::ConvexHullTrickAddMonotone<long long, true> cht;
	cht.add(0, 0);
	rep2(i, 1, n + 1) {
		dp[i] = cht.query(i - 1) - (long long)a*(i - 1);
		dp[i] += (long long)(i - 1) * i / 2 * b + d[i - 1];
		cht.add(-(long long)i * b, dp[i] + (long long)i * a
			+ ((long long)i * i - i) / 2 * b);
	}
	long long ans = LINF;
	rep(i, n + 1) {
		long long add = -1 * ((long long)n - i) *a + ((long long)n - i) *(n - i + 1) / 2 * b;
		chmin(ans, dp[i] + add);
	}
	cout << ans + w << endl;
	return 0;
}