結果

問題 No.409 ダイエット
ユーザー satanic
提出日時 2016-08-16 15:47:35
言語 C++14
(gcc 6.3.0)
結果
AC  
実行時間 41 ms
コード長 5661 Byte
コンパイル時間 1290 ms
使用メモリ 10340 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1smallsmall01.txt AC 4 ms
1520 KB
1smallsmall02.txt AC 5 ms
1524 KB
1smallsmall03.txt AC 4 ms
1528 KB
1smallsmall04.txt AC 3 ms
1524 KB
1smallsmall05.txt AC 4 ms
1524 KB
1smallsmall06.txt AC 4 ms
1528 KB
1smallsmall07.txt AC 4 ms
1528 KB
1smallsmall08.txt AC 4 ms
1504 KB
1smallsmall09.txt AC 4 ms
1528 KB
1smallsmall10.txt AC 4 ms
1524 KB
1smallsmall11.txt AC 3 ms
1524 KB
1smallsmall12.txt AC 3 ms
1524 KB
1smallsmall13.txt AC 4 ms
1524 KB
1smallsmall14.txt AC 4 ms
1528 KB
1smallsmall15.txt AC 4 ms
1524 KB
1smallsmall16.txt AC 4 ms
1524 KB
1smallsmall17.txt AC 5 ms
1520 KB
1smallsmall18.txt AC 3 ms
1524 KB
1smallsmall19.txt AC 4 ms
1524 KB
1smallsmall20.txt AC 4 ms
1524 KB
2smalllarge01.txt AC 3 ms
1524 KB
2smalllarge02.txt AC 3 ms
1528 KB
2smalllarge03.txt AC 4 ms
1528 KB
2smalllarge04.txt AC 4 ms
1524 KB
2smalllarge05.txt AC 3 ms
1520 KB
2smalllarge06.txt AC 4 ms
1528 KB
2smalllarge07.txt AC 3 ms
1528 KB
2smalllarge08.txt AC 4 ms
1524 KB
2smalllarge09.txt AC 4 ms
1520 KB
2smalllarge10.txt AC 4 ms
1528 KB
2smalllarge11.txt AC 4 ms
1524 KB
2smalllarge12.txt AC 3 ms
1520 KB
2smalllarge13.txt AC 4 ms
1528 KB
2smalllarge14.txt AC 4 ms
1528 KB
2smalllarge15.txt AC 5 ms
1520 KB
3middle01.txt AC 5 ms
1620 KB
3middle02.txt AC 4 ms
1628 KB
3middle03.txt AC 4 ms
1656 KB
3middle04.txt AC 5 ms
1656 KB
3middle05.txt AC 4 ms
1624 KB
3middle06.txt AC 4 ms
1616 KB
3middle07.txt AC 4 ms
1664 KB
3middle08.txt AC 4 ms
1664 KB
3middle09.txt AC 4 ms
1668 KB
3middle10.txt AC 5 ms
1664 KB
3middle11.txt AC 4 ms
1664 KB
3middle12.txt AC 4 ms
1628 KB
3middle13.txt AC 4 ms
1664 KB
3middle14.txt AC 4 ms
1656 KB
3middle15.txt AC 5 ms
1668 KB
3middle16.txt AC 4 ms
1624 KB
3middle17.txt AC 4 ms
1664 KB
3middle18.txt AC 5 ms
1672 KB
3middle19.txt AC 7 ms
1628 KB
3middle20.txt AC 6 ms
1616 KB
4largesmall01.txt AC 28 ms
4884 KB
4largesmall02.txt AC 29 ms
4732 KB
4largesmall03.txt AC 40 ms
8996 KB
4largesmall04.txt AC 22 ms
4736 KB
4largesmall05.txt AC 24 ms
5132 KB
4largesmall06.txt AC 17 ms
4428 KB
4largesmall07.txt AC 33 ms
8160 KB
4largesmall08.txt AC 38 ms
8624 KB
4largesmall09.txt AC 32 ms
8728 KB
4largesmall10.txt AC 20 ms
4860 KB
4largesmall11.txt AC 34 ms
6252 KB
4largesmall12.txt AC 35 ms
9652 KB
4largesmall13.txt AC 28 ms
9280 KB
4largesmall14.txt AC 32 ms
5108 KB
4largesmall15.txt AC 31 ms
8756 KB
5largelarge01.txt AC 37 ms
8324 KB
5largelarge02.txt AC 25 ms
4768 KB
5largelarge03.txt AC 41 ms
8696 KB
5largelarge04.txt AC 40 ms
10340 KB
5largelarge05.txt AC 28 ms
8496 KB
5largelarge06.txt AC 39 ms
9140 KB
5largelarge07.txt AC 30 ms
8340 KB
5largelarge08.txt AC 23 ms
3928 KB
5largelarge09.txt AC 25 ms
8920 KB
5largelarge10.txt AC 20 ms
4744 KB
5largelarge11.txt AC 39 ms
8340 KB
5largelarge12.txt AC 38 ms
9200 KB
5largelarge13.txt AC 30 ms
8416 KB
5largelarge14.txt AC 34 ms
9320 KB
5largelarge15.txt AC 26 ms
5176 KB
system_test1.txt AC 17 ms
3436 KB
system_test2.txt AC 27 ms
4304 KB
system_test3.txt AC 19 ms
2992 KB
system_test4.txt AC 31 ms
4372 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <algorithm>
#include <bitset>
#include <cassert>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <vector>
#include <array>
#include <chrono>
#include <random>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); }
#define OUT(d) std::cout<<d;
#define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<d;
#define SOUT(n, c, d) std::cout<<std::setw(n)<<std::setfill(c)<<d;
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define ENDL std::cout<<std::endl;
#define FLUSH std::cout<<std::flush;
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i;
#define ALL(a) (a).begin(),(a).end()
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
#define PAIR std::pair<int, int>
#define IN(a, x, b) (a<=x && x<=b)
#define IN2(a0, y, a1, b0, x, b1) (a0<=y && y<a1 && b0<=x && x<b1)
#define SHOW(d) {std::cout << #d << "\t:" << d << "\n";}
#define SHOWVECTOR(v) {std::cout << #v << "\t:";for(const auto& i : v){std::cout << i << " ";}std::cout << "\n";}
#define SHOWVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout << j << " ";}std::cout << "\n";}}
#define SHOWPAIRVECTOR2(v) {std::cout << #v << "\t:\n";for(const auto& i : v){for(const auto& j : i){std::cout<<'('<<j.first<<", "<<j.second<<") ";}std::cout << "\n";}}
#define SHOWPAIRVECTOR(v) {for(const auto& i:v){std::cout<<'('<<i.first<<", "<<i.second<<") ";}std::cout<<"\n";}
#define CHECKTIME(state) {auto start=std::chrono::system_clock::now();state();auto end=std::chrono::system_clock::now();auto res=std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();std::cerr<<"[Time:"<<res<<"ns  ("<<res/(1.0e9)<<"s)]\n";}
#define SHOWQUEUE(a) {std::queue<decltype(a.front())> tmp(a);std::cout << #a << "\t:";for(int i=0; i<static_cast<int>(a.size()); ++i){std::cout << tmp.front() << "\n";tmp.pop();}std::cout << "\n";}

//#define int ll
using ll = long long;
constexpr int INFINT = 1 << 30;
constexpr ll INFLL = 1LL << 60;
constexpr double EPS = 0.0000001;
constexpr int MOD = 1000000007;

/*
DP[i] = i日目にドーナツを食べた時の体重の最小値
      = min_{t:0~i-1}(DP[t] + -A*(i-t-1)+1/2*(i-t-1)*(i-t)*B + D[i])
      = min_{t:0~i-1}(DP[t] + tA + (-2it+t^2+t)B/2) -A(i-1) + (i^2-i)B/2 + D[i]
      = min_{t:0~i-1}(DP[t] + tA + (t^2+t)B/2 -itB) -A(i-1) + (i^2-i)B/2 + D[i]
      = min_{t:0~i-1}(F[t]-iG[t]) -A(i-1) + (i^2-i)B/2 + D[i]
          (F[t]=DP[t] + tA + (t^2+t)B/2 ,  G[t]=tB)
*/
ll dp[300005];

template<typename T>
class ConvecHullTrick {
private:
	// 直線群(配列)
	std::vector<std::pair<T, T>> lines;
	// 最小値(最大値)を求めるxが単調であるか
	bool isMonotonicX;
	// 最小/最大を判断する関数
	std::function<bool(T l, T r)> comp;

public:
	// コンストラクタ ( クエリが単調であった場合はflag = trueとする )
	ConvecHullTrick(bool flagX = false, std::function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r; })
		:isMonotonicX(flagX), comp(compFunc)  {
		lines.emplace_back(0, 0);
	};

	// 直線l1, l2, l3のうちl2が不必要であるかどうか
	bool check(std::pair<T, T> l1, std::pair<T, T> l2, std::pair<T, T> l3) {
		if (l1 < l3) std::swap(l1, l3);
		return (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first);
	}

	// 直線y=ax+bを追加する
	void add(T a, T b) {
		std::pair<T, T> line(a, b);
		while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), line))
			lines.pop_back();
		lines.emplace_back(line);
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(int i, T x) {
		return lines[i].first * x + lines[i].second;
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(std::pair<T, T> line, T x) {
		return line.first * x + line.second;
	}

	// 直線群の中でxの時に最小(最大)となる値を返す
	T get(T x) {
		// 最小値(最大値)クエリにおけるxが単調
		if (isMonotonicX) {
			static int head = 0;
			while (lines.size() - head >= 2 && comp(f(head, x), f(head + 1, x)))
				++head;
			return f(head, x);
		}
		else {
			int low = -1, high = lines.size() - 1;
			while (high - low > 1) {
				int mid = (high + low) / 2;
				(comp(f(mid, x), f(mid + 1, x)) ? low : high) = mid;
			}
			return f(high, x);
		}
	}
};

signed main() {
	INIT;
	VAR(ll, n, a, b, w);
	VEC(int, d, n);
	ConvecHullTrick<ll> cht(true);

	dp[0] = 0;
	FOR(i, 1, n + 1) {
		dp[i] = cht.get(i - 1) - (i - 1)*a + ((ll)(i - 1) * i) / 2 * b + d[i - 1];
		cht.add(-i*b, dp[i] + i*a + (ll)(i - 1) * i / 2 * b);
	}
	/*
	REP(i, n + 1) {
		OUT(dp[i] + w)SP;
	}BR;
	*/
	ll ans = INFLL;
	REP(i, n + 1) {
		ans = std::min(ans, dp[i] + (-(n - i)*a + (n - i)*(n - i + 1) / 2 * b));
	}
	OUT(ans + w);
	return 0;
}
0