#723779 (C++17) No.409 ダイエット

• 問題: No.409 ダイエット
• ユーザー: nanophoto12
• 提出日時: 2021-12-12 20:48:57
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 383 ms / 2,000 ms
• コード長: 4,704 bytes
• コンパイル時間: 5,406 ms
• コンパイル使用メモリ: 266,320 KB
• 実行使用メモリ: 31,468 KB
• 最終ジャッジ日時: 2023-09-28 14:09:19
• 合計ジャッジ時間: 16,919 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	2 ms; 4,376 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	2 ms; 4,376 KB
testcase_11	AC	2 ms; 4,380 KB
testcase_12	AC	1 ms; 4,380 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	1 ms; 4,376 KB
testcase_15	AC	1 ms; 4,376 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	AC	2 ms; 4,376 KB
testcase_18	AC	2 ms; 4,376 KB
testcase_19	AC	2 ms; 4,380 KB
testcase_20	AC	1 ms; 4,380 KB
testcase_21	AC	1 ms; 4,376 KB
testcase_22	AC	1 ms; 4,376 KB
testcase_23	AC	2 ms; 4,376 KB
testcase_24	AC	2 ms; 4,380 KB
testcase_25	AC	2 ms; 4,376 KB
testcase_26	AC	1 ms; 4,380 KB
testcase_27	AC	2 ms; 4,376 KB
testcase_28	AC	1 ms; 4,380 KB
testcase_29	AC	1 ms; 4,376 KB
testcase_30	AC	2 ms; 4,376 KB
testcase_31	AC	1 ms; 4,376 KB
testcase_32	AC	1 ms; 4,376 KB
testcase_33	AC	1 ms; 4,376 KB
testcase_34	AC	2 ms; 4,376 KB
testcase_35	AC	3 ms; 4,376 KB
testcase_36	AC	3 ms; 4,376 KB
testcase_37	AC	3 ms; 4,380 KB
testcase_38	AC	3 ms; 4,380 KB
testcase_39	AC	4 ms; 4,376 KB
testcase_40	AC	3 ms; 4,376 KB
testcase_41	AC	4 ms; 4,380 KB
testcase_42	AC	4 ms; 4,376 KB
testcase_43	AC	3 ms; 4,380 KB
testcase_44	AC	3 ms; 4,376 KB
testcase_45	AC	3 ms; 4,380 KB
testcase_46	AC	3 ms; 4,380 KB
testcase_47	AC	4 ms; 4,376 KB
testcase_48	AC	4 ms; 4,376 KB
testcase_49	AC	3 ms; 4,380 KB
testcase_50	AC	3 ms; 4,376 KB
testcase_51	AC	4 ms; 4,380 KB
testcase_52	AC	4 ms; 4,380 KB
testcase_53	AC	3 ms; 4,376 KB
testcase_54	AC	3 ms; 4,380 KB
testcase_55	AC	144 ms; 15,736 KB
testcase_56	AC	67 ms; 7,628 KB
testcase_57	AC	359 ms; 31,468 KB
testcase_58	AC	132 ms; 15,220 KB
testcase_59	AC	165 ms; 14,676 KB
testcase_60	AC	115 ms; 13,416 KB
testcase_61	AC	295 ms; 25,988 KB
testcase_62	AC	352 ms; 31,384 KB
testcase_63	AC	275 ms; 24,396 KB
testcase_64	AC	127 ms; 13,704 KB
testcase_65	AC	246 ms; 17,020 KB
testcase_66	AC	318 ms; 26,476 KB
testcase_67	AC	249 ms; 23,916 KB
testcase_68	AC	162 ms; 14,600 KB
testcase_69	AC	268 ms; 22,568 KB
testcase_70	AC	291 ms; 24,404 KB
testcase_71	AC	158 ms; 15,812 KB
testcase_72	AC	383 ms; 30,876 KB
testcase_73	AC	294 ms; 20,188 KB
testcase_74	AC	214 ms; 20,120 KB
testcase_75	AC	312 ms; 22,560 KB
testcase_76	AC	248 ms; 22,296 KB
testcase_77	AC	123 ms; 10,640 KB
testcase_78	AC	193 ms; 18,776 KB
testcase_79	AC	129 ms; 13,148 KB
testcase_80	AC	360 ms; 29,536 KB
testcase_81	AC	304 ms; 21,488 KB
testcase_82	AC	243 ms; 21,036 KB
testcase_83	AC	255 ms; 21,284 KB
testcase_84	AC	173 ms; 13,080 KB
testcase_85	AC	16 ms; 4,608 KB
testcase_86	AC	171 ms; 13,896 KB
testcase_87	AC	303 ms; 25,420 KB
testcase_88	AC	92 ms; 9,664 KB
testcase_89	AC	154 ms; 8,888 KB
testcase_90	AC	71 ms; 6,492 KB
testcase_91	AC	168 ms; 9,144 KB

ソースコード

#include <bits/stdc++.h>
#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)

template<typename T>
static inline void chmin(T& ref, const T  value) {
	if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
	if (ref < value) ref = value;
}

#include <atcoder/all>

using namespace atcoder;

typedef modint998244353 mint;

typedef ll CHT_TYPE;

class ConvexHullTrickDynamic {
private:
	// 直線 **************************************************************
	struct Line {
		CHT_TYPE a, b; // y = ax + b
		mutable std::function<const Line* ()> getSuc; // 次の直線へのポインタ (ソートで用いる)

		bool operator<(const Line& rhs) const {
			// 取得クエリでは次の直線との差分でソート
			if (rhs.b == IS_QUERY) {
				const Line* suc = getSuc();
				if (suc == nullptr) return false;
				const CHT_TYPE& x = rhs.a;
				return (suc->a - a) * x + suc->b - b > 0;
			}
			if (b == IS_QUERY) {
				const Line* suc = rhs.getSuc();
				if (suc == nullptr) return true;
				const CHT_TYPE& x = a;
				return (suc->a - rhs.a) * x + suc->b - rhs.b < 0;
			}

			// 通常の直線どうしは傾きソート
			return a < rhs.a;
		}
	};

	// 直線集合 **********************************************************
	class LinesSet {
	private:
		// true -> 最小値クエリ, false -> 最大値クエリ
		bool flagMin;
		std::multiset<Line> lines;
	public:
		// コンストラクタ ( 第一引数falseで最大値クエリ,デフォルトで最小値クエリ )
		LinesSet(bool flagMin = true) : flagMin(flagMin) {};

		// 直線lが不必要であるかどうか
		bool isBad(std::multiset<Line>::iterator l) {
			const auto&& nel = std::next(l);
			if (l == lines.begin()) { // lが傾き最小のとき
				if (nel == lines.end()) return false; // lしかないなら必要
				return l->a == nel->a && l->b <= nel->b;
			}
			else {
				const auto&& prl = std::prev(l);
				if (nel == lines.end()) return l->a == prl->a && l->b <= prl->b;
				return (prl->b - l->b) * (nel->a - l->a) >= (nel->b - l->b) * (prl->a - l->a);
			}
		}

		// 直線y=ax+bを追加する
		inline void add(CHT_TYPE a, CHT_TYPE b) {
			if (flagMin) a = -a, b = -b;
			auto&& it = lines.insert(Line{ a, b });
			it->getSuc = [=] { return (std::next(it) == lines.end() ? nullptr : &*std::next(it)); };
			if (isBad(it)) { lines.erase(it); return; }
			while (std::next(it) != lines.end() && isBad(std::next(it))) lines.erase(std::next(it));
			while (it != lines.begin() && isBad(std::prev(it))) lines.erase(std::prev(it));
		}

		// 直線群の中でxの時に最小(最大)となる値を返す
		inline CHT_TYPE get(CHT_TYPE x) {
			auto&& l = *lines.lower_bound(Line{ x, IS_QUERY });
			if (flagMin) return -l.a * x - l.b;
			else return l.a * x + l.b;
		}
	};

	static const CHT_TYPE IS_QUERY = std::numeric_limits<CHT_TYPE>::lowest();
	LinesSet linesSet;

public:
	// コンストラクタ ( 第一引数falseで最大値クエリ,デフォルトで最小値クエリ )
	ConvexHullTrickDynamic(bool flagMin = true) : linesSet(flagMin) {}
	// 直線y=ax+bを追加する
	inline void add(CHT_TYPE a, CHT_TYPE b) { linesSet.add(a, b); }
	// あるxのときの直線集合での最小値を求める
	inline CHT_TYPE get(CHT_TYPE x) { return linesSet.get(x); }
};

int main() {
	//dp[i]...i日目に最後のドーナツをたべたときの最小値
	//dp[i]...min(dp[0] + b * (1 + 2 + 3 + ... i) - a * i,
	//   dp[1] + b * (1 + 2 + 3 + ... + i-1) - a * (i-1)
	//dp[j] + (i-j) * (i-j+1)/2 - a * (i-j);
	//a = (-j+1) + (-j) / 2
	ll n, a, b, w;
	cin >> n >> a >> b >> w;
	vector<ll> ds(n + 2, 0);
	rep(i, n) cin >> ds[i + 1];
	vector<ll> dp(n + 2, 1e15);
	dp[0] = 0;
	ConvexHullTrickDynamic cht;
	cht.add(-b * 0 + b * (-0 + 1) - a * 2,
		dp[0] * 2 + b * 0 * (0 - 1) + 2 * a * 0);
	for (int i = 1; i <= n + 1; i++) {
		ll low = 1e15;
		ll ci = i - 1;
		ll d = (cht.get(ci) + b * ci * ci) / 2;
		//for (int j = 0; j < i; j++) {
			//ll p = dp[j] + b * (ci - j) * (ci - j + 1) / 2 - a * (ci - j);
			//dp[j] + b * (-j+1) ci / 2+ -b * j * ci / 2+ b * ci * ci / 2+ b * j * (j-1) / 2
			// -a * ci + a * j;
			//A = - b * j / 2+ b * (-j + 1) / 2- a;
			//B = dp[j] + b * j * (j-1) / 2 + a * j
			//C = b * ci * ci / 2
			//chmin(low, p);
		//}
		dp[i] = d + ds[i];
		cht.add(-b * i + b * (-i + 1) - a * 2,
			dp[i] * 2 + b * i * (i - 1) + 2 * a * i);
	}
	ll ans = w + dp[n + 1];
	cout << ans << endl;
	return 0;
}