結果

問題 No.409 ダイエット
ユーザー anta
提出日時 2016-08-05 23:14:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 3,799 bytes
コンパイル時間 2,055 ms
コンパイル使用メモリ 186,072 KB
実行使用メモリ 28,464 KB
最終ジャッジ日時 2024-06-26 09:39:31
合計ジャッジ時間 9,624 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 92
権限があれば一括ダウンロードができます

ソースコード

diff # 

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