結果

問題 No.409 ダイエット
ユーザー satanic
提出日時 2016-08-12 16:46:37
言語 C++14
(gcc 7.1.0)
結果
AC  
実行時間 517 ms
コード長 4261 Byte
コンパイル時間 1137 ms
使用メモリ 6052 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1smallsmall01.txt AC 4 ms
1540 KB
1smallsmall02.txt AC 5 ms
1540 KB
1smallsmall03.txt AC 6 ms
1536 KB
1smallsmall04.txt AC 5 ms
1540 KB
1smallsmall05.txt AC 4 ms
1536 KB
1smallsmall06.txt AC 4 ms
1536 KB
1smallsmall07.txt AC 4 ms
1536 KB
1smallsmall08.txt AC 4 ms
1528 KB
1smallsmall09.txt AC 4 ms
1540 KB
1smallsmall10.txt AC 4 ms
1536 KB
1smallsmall11.txt AC 3 ms
1540 KB
1smallsmall12.txt AC 4 ms
1536 KB
1smallsmall13.txt AC 4 ms
1536 KB
1smallsmall14.txt AC 4 ms
1536 KB
1smallsmall15.txt AC 4 ms
1536 KB
1smallsmall16.txt AC 4 ms
1524 KB
1smallsmall17.txt AC 4 ms
1536 KB
1smallsmall18.txt AC 3 ms
1540 KB
1smallsmall19.txt AC 4 ms
1536 KB
1smallsmall20.txt AC 3 ms
1540 KB
2smalllarge01.txt AC 4 ms
1540 KB
2smalllarge02.txt AC 3 ms
1536 KB
2smalllarge03.txt AC 4 ms
1536 KB
2smalllarge04.txt AC 4 ms
1540 KB
2smalllarge05.txt AC 4 ms
1540 KB
2smalllarge06.txt AC 4 ms
1540 KB
2smalllarge07.txt AC 3 ms
1540 KB
2smalllarge08.txt AC 4 ms
1536 KB
2smalllarge09.txt AC 4 ms
1536 KB
2smalllarge10.txt AC 3 ms
1540 KB
2smalllarge11.txt AC 4 ms
1540 KB
2smalllarge12.txt AC 4 ms
1536 KB
2smalllarge13.txt AC 4 ms
1540 KB
2smalllarge14.txt AC 4 ms
1536 KB
2smalllarge15.txt AC 4 ms
1540 KB
3middle01.txt AC 8 ms
1580 KB
3middle02.txt AC 9 ms
1588 KB
3middle03.txt AC 9 ms
1588 KB
3middle04.txt AC 9 ms
1584 KB
3middle05.txt AC 10 ms
1584 KB
3middle06.txt AC 9 ms
1584 KB
3middle07.txt AC 10 ms
1584 KB
3middle08.txt AC 10 ms
1584 KB
3middle09.txt AC 9 ms
1580 KB
3middle10.txt AC 9 ms
1584 KB
3middle11.txt AC 10 ms
1584 KB
3middle12.txt AC 9 ms
1588 KB
3middle13.txt AC 9 ms
1584 KB
3middle14.txt AC 9 ms
1584 KB
3middle15.txt AC 10 ms
1588 KB
3middle16.txt AC 9 ms
1588 KB
3middle17.txt AC 9 ms
1588 KB
3middle18.txt AC 9 ms
1584 KB
3middle19.txt AC 9 ms
1584 KB
3middle20.txt AC 9 ms
1584 KB
4largesmall01.txt AC 258 ms
3676 KB
4largesmall02.txt AC 24 ms
3680 KB
4largesmall03.txt AC 517 ms
6052 KB
4largesmall04.txt AC 220 ms
3412 KB
4largesmall05.txt AC 313 ms
4200 KB
4largesmall06.txt AC 201 ms
3148 KB
4largesmall07.txt AC 442 ms
5260 KB
4largesmall08.txt AC 473 ms
5528 KB
4largesmall09.txt AC 442 ms
5264 KB
4largesmall10.txt AC 236 ms
3416 KB
4largesmall11.txt AC 463 ms
5524 KB
4largesmall12.txt AC 493 ms
5792 KB
4largesmall13.txt AC 379 ms
4736 KB
4largesmall14.txt AC 308 ms
4208 KB
4largesmall15.txt AC 434 ms
5264 KB
5largelarge01.txt AC 420 ms
4996 KB
5largelarge02.txt AC 239 ms
3416 KB
5largelarge03.txt AC 511 ms
5788 KB
5largelarge04.txt AC 465 ms
5524 KB
5largelarge05.txt AC 296 ms
3944 KB
5largelarge06.txt AC 474 ms
5528 KB
5largelarge07.txt AC 343 ms
4472 KB
5largelarge08.txt AC 228 ms
3412 KB
5largelarge09.txt AC 260 ms
3680 KB
5largelarge10.txt AC 218 ms
3152 KB
5largelarge11.txt AC 473 ms
5524 KB
5largelarge12.txt AC 458 ms
5524 KB
5largelarge13.txt AC 360 ms
4468 KB
5largelarge14.txt AC 380 ms
4736 KB
5largelarge15.txt AC 312 ms
3944 KB
system_test1.txt AC 175 ms
2888 KB
system_test2.txt AC 348 ms
4472 KB
system_test3.txt AC 161 ms
2888 KB
system_test4.txt AC 386 ms
4736 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <algorithm>
#include <bitset>
#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 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;

// min[i] := min_{0<=k<=1419}(dp[i][k])
ll min[300005];

signed main() {
	INIT;
	VAR(ll, n, a, b, w);
	VEC(ll, d, n);

	// ストレス太りしない => ずっと断食すべき(過激派)
	if (b == 0) {
		OUT(w - a*n)BR;
		return 0;
	}

	// ストレス太りする(b>=1)
	// このとき、i日間の断食による体重の変化量は最大で、b*i(i+1)/2 であり、
	// d[i]は最大10^6、 bは最小1であるから、
	//     i(i+1)/2 = 10^6
	//     i^2 + i - 2*10^6 = 0
	//     i = (-1 + √(1+8*10^6))/2  (∵ i>=0)
	//       ~ -1/2 + √2 * 10^3  (∵ 1<<8*10^6)
	//       ~ 1414
	// より、1415日以上断食すると、それ以降の日ではどんなドーナツを食べるよりも体重が増加する
	//   ∴ 断食日数については1415日強だけ考えればよい
	ll dp[2][1420] = {};
	// Rem. 配列の1次引数は、
	//      片方を前日の結果として残して、もう片方を決めていくための作業領域
	//       (dp[300005][1420]とすると大きすぎるため)
	

	// 始め、体重の変化量は明らかに0
	// (既に0で初期化されている)
	// dp[0][0] = 0


	// 最大で、
	//     300000 * 1418 ~ 4*10^8
	// 回のループ(ギリギリ間に合う?)
	FOR(i, 1, n+1) {
		// ドーナツを食べるとき
		dp[i%2][0] = min[i-1] + d[i-1];
		min[i] = dp[i%2][0];

		// ドーナツを食べないとき
		FOR(j, 1, 1419) {
			dp[i%2][j] = dp[!(i%2)][j-1] - a + j*b;
			min[i] = std::min(min[i], dp[i%2][j]);
		}
	}

	OUT(min[n] + w);
	return 0;
}
0