#108753 (C++14) No.409 ダイエット

提出ソース

結果

問題	No.409 ダイエット
ユーザー	anta
提出日時	2016-08-05 23:14:56
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	198 ms / 2,000 ms
コード長	3,799 bytes
コンパイル時間	2,092 ms
コンパイル使用メモリ	182,392 KB
実行使用メモリ	27,368 KB
最終ジャッジ日時	2023-09-08 16:49:50
合計ジャッジ時間	9,924 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	1 ms 4,380 KB
testcase_09	AC	1 ms 4,380 KB
testcase_10	AC	1 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	1 ms 4,376 KB
testcase_15	AC	2 ms 4,380 KB
testcase_16	AC	1 ms 4,380 KB
testcase_17	AC	2 ms 4,376 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	2 ms 4,380 KB
testcase_21	AC	1 ms 4,376 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	1 ms 4,380 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	2 ms 4,380 KB
testcase_27	AC	2 ms 4,376 KB
testcase_28	AC	1 ms 4,376 KB
testcase_29	AC	1 ms 4,380 KB
testcase_30	AC	2 ms 4,376 KB
testcase_31	AC	2 ms 4,376 KB
testcase_32	AC	2 ms 4,376 KB
testcase_33	AC	2 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,376 KB
testcase_38	AC	3 ms 4,380 KB
testcase_39	AC	3 ms 4,376 KB
testcase_40	AC	3 ms 4,376 KB
testcase_41	AC	3 ms 4,380 KB
testcase_42	AC	3 ms 4,376 KB
testcase_43	AC	3 ms 4,376 KB
testcase_44	AC	3 ms 4,376 KB
testcase_45	AC	3 ms 4,376 KB
testcase_46	AC	3 ms 4,376 KB
testcase_47	AC	3 ms 4,376 KB
testcase_48	AC	3 ms 4,380 KB
testcase_49	AC	3 ms 4,376 KB
testcase_50	AC	3 ms 4,376 KB
testcase_51	AC	3 ms 4,376 KB
testcase_52	AC	3 ms 4,376 KB
testcase_53	AC	3 ms 4,380 KB
testcase_54	AC	3 ms 4,380 KB
testcase_55	AC	92 ms 14,584 KB
testcase_56	AC	170 ms 26,576 KB
testcase_57	AC	192 ms 26,368 KB
testcase_58	AC	74 ms 10,136 KB
testcase_59	AC	120 ms 15,936 KB
testcase_60	AC	67 ms 9,920 KB
testcase_61	AC	164 ms 17,264 KB
testcase_62	AC	178 ms 26,996 KB
testcase_63	AC	165 ms 17,020 KB
testcase_64	AC	92 ms 15,040 KB
testcase_65	AC	189 ms 27,044 KB
testcase_66	AC	197 ms 27,244 KB
testcase_67	AC	137 ms 16,812 KB
testcase_68	AC	118 ms 16,444 KB
testcase_69	AC	163 ms 16,780 KB
testcase_70	AC	156 ms 16,264 KB
testcase_71	AC	83 ms 9,988 KB
testcase_72	AC	198 ms 26,588 KB
testcase_73	AC	187 ms 17,620 KB
testcase_74	AC	107 ms 15,396 KB
testcase_75	AC	196 ms 27,368 KB
testcase_76	AC	122 ms 16,792 KB
testcase_77	AC	86 ms 10,164 KB
testcase_78	AC	94 ms 16,152 KB
testcase_79	AC	75 ms 9,780 KB
testcase_80	AC	187 ms 25,908 KB
testcase_81	AC	182 ms 17,448 KB
testcase_82	AC	127 ms 16,436 KB
testcase_83	AC	141 ms 16,020 KB
testcase_84	AC	118 ms 15,924 KB
testcase_85	AC	13 ms 4,428 KB
testcase_86	AC	116 ms 15,484 KB
testcase_87	AC	155 ms 17,120 KB
testcase_88	AC	64 ms 8,992 KB
testcase_89	AC	134 ms 16,028 KB
testcase_90	AC	59 ms 9,528 KB
testcase_91	AC	145 ms 15,644 KB

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

ソースコード

raw source code

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct IncrementalEnvelope {
	typedef pair<int, long long> P;
	typedef long long X;
	vector<P> ps;
	vector<pair<X, P> > seq;
	vector<int> sizes;

	void clear() {
		ps.clear();
		seq.clear();
		sizes.clear();
	}

	bool empty() const { return ps.empty(); }

	struct ComparePoint {
		bool operator()(const P &a, const P &b) const {
			if(a.first != b.first)
				return a.first < b.first;
			else
				return a.second > b.second;
		}
	};

	void insert(const P &p) {
		int n = (int)ps.size();
		ps.push_back(p);
		seq.push_back(make_pair(-1, P()));
		int i;
		for(i = 0; n >> i & 1; ++ i) {
			int m = 1 << i;
			inplace_merge(ps.end() - m * 2, ps.end() - m, ps.end(), ComparePoint());
			sizes[i] = 0;
		}
		if(sizes.size() == i)
			sizes.push_back(0);
		assert(sizes[i] == 0);
		int m = 1 << i;
		makeEnvelope(&*(seq.end() - m), sizes[i], &*(ps.end() - m), &ps[0] + ps.size());
	}

	long long findMax(X x) const {
		long long r = numeric_limits<ll>::min();
		const pair<X, P> *stk = &seq[0] + seq.size();
		rep(i, sizes.size()) {
			int n = sizes[i];
			if(n != 0) {
				stk -= 1 << i;
				long long val = findMaxEnvelope(stk, n, x);
				if(r < val)
					r = val;
			}
		}
		return r;
	}

private:
	static long long findMaxEnvelope(const pair<X, P> *stk, int size, X x) {
		int l = 0, u = size - 1;
		while(u - l > 0) {
			int mid = (l + u + 1) / 2;
			if(stk[mid].first <= x)
				l = mid;
			else
				u = mid - 1;
		}
		P p = stk[l].second;
		return evaluate(p, x);
	}

	static void makeEnvelope(pair<X, P> *stk, int &sp, const P *begin, const P *end) {
		sp = 0;
		for(const P *it = begin; it != end; ++ it) {
			P p = *it;
			if(sp > 0 && p.first == stk[sp - 1].second.first)
				continue;
			for(; sp > 0; -- sp) {
				X x = stk[sp - 1].first;
				if(evaluate(p, x) <= evaluate(stk[sp - 1].second, x))
					break;
			}
			long long x;
			if(sp == 0)
				x = 0;
			else
				x = crosspoint(stk[sp - 1].second, p);
			assert(x >= 0);
			if(x > numeric_limits<X>::max())
				x = numeric_limits<X>::max();
			stk[sp ++] = make_pair((X)x, p);
		}
	}

	static long long evaluate(const P &p, X x) {
		return (long long)x * p.first + p.second;
	}

	static long long crosspoint(const P &p, const P &q) {
		long long num = p.second - q.second;
		int den = q.first - p.first;
		assert(den > 0);
		return (num / den + (num > 0 && num % den != 0));
	}

public:
	void swap(IncrementalEnvelope &that) {
		ps.swap(that.ps);
		seq.swap(that.seq);
		sizes.swap(that.sizes);
	}
};

int main() {
	int N; int A; int B; int W;
	while(~scanf("%d%d%d%d", &N, &A, &B, &W)) {
		vector<int> D(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &D[i]);
		ll ans = W + (ll)N * (N + 1) / 2 * B - (ll)N * A;
		IncrementalEnvelope env;
		vector<ll> dp(N + 1, INFL);
		dp[0] = W * 2;
		env.insert(make_pair(0, -dp[0]));
		rep(i, N) {
			ll x = INFL;
			ll a1 = -2LL * i * B;
			ll a0 = -(ll)i * A * 2 + (ll)i * i * B + (ll)i * B;
			x = -env.findMax(-a1);
			x += a0;
			x += D[i] * 2;
			{
				int w = N - (i + 1);
				amin(ans, x / 2 - (ll)w * A + (ll)w * (w + 1) / 2 * B);
			}
			dp[i + 1] = x + (ll)(i + 1) * A * 2 + ((ll)(i + 1) * (i + 1) - (i + 1)) * B;
			env.insert(make_pair((i + 1), -dp[i + 1]));
		}
		printf("%lld\n", ans);
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード