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

提出ソース

結果

問題	No.409 ダイエット
ユーザー	0w1
提出日時	2019-11-26 12:27:36
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	90 ms / 2,000 ms
コード長	1,725 bytes
コンパイル時間	788 ms
コンパイル使用メモリ	85,488 KB
実行使用メモリ	13,536 KB
最終ジャッジ日時	2023-08-06 13:41:59
合計ジャッジ時間	7,117 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,364 KB
testcase_01	AC	2 ms 5,368 KB
testcase_02	AC	2 ms 5,368 KB
testcase_03	AC	2 ms 5,408 KB
testcase_04	AC	2 ms 5,480 KB
testcase_05	AC	2 ms 5,372 KB
testcase_06	AC	2 ms 5,388 KB
testcase_07	AC	2 ms 5,392 KB
testcase_08	AC	2 ms 5,364 KB
testcase_09	AC	2 ms 5,548 KB
testcase_10	AC	2 ms 5,352 KB
testcase_11	AC	2 ms 5,356 KB
testcase_12	AC	2 ms 5,352 KB
testcase_13	AC	2 ms 5,420 KB
testcase_14	AC	2 ms 5,388 KB
testcase_15	AC	2 ms 5,420 KB
testcase_16	AC	2 ms 5,368 KB
testcase_17	AC	2 ms 5,372 KB
testcase_18	AC	3 ms 5,364 KB
testcase_19	AC	2 ms 5,372 KB
testcase_20	AC	2 ms 5,368 KB
testcase_21	AC	2 ms 5,424 KB
testcase_22	AC	2 ms 5,372 KB
testcase_23	AC	2 ms 5,392 KB
testcase_24	AC	2 ms 5,652 KB
testcase_25	AC	2 ms 5,540 KB
testcase_26	AC	2 ms 5,372 KB
testcase_27	AC	3 ms 5,368 KB
testcase_28	AC	2 ms 5,548 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,368 KB
testcase_31	AC	2 ms 5,512 KB
testcase_32	AC	2 ms 5,544 KB
testcase_33	AC	2 ms 5,540 KB
testcase_34	AC	3 ms 5,368 KB
testcase_35	AC	3 ms 5,424 KB
testcase_36	AC	3 ms 5,584 KB
testcase_37	AC	3 ms 5,412 KB
testcase_38	AC	3 ms 5,408 KB
testcase_39	AC	3 ms 5,516 KB
testcase_40	AC	3 ms 5,412 KB
testcase_41	AC	3 ms 5,588 KB
testcase_42	AC	3 ms 5,432 KB
testcase_43	AC	3 ms 5,412 KB
testcase_44	AC	3 ms 5,404 KB
testcase_45	AC	3 ms 5,408 KB
testcase_46	AC	3 ms 5,416 KB
testcase_47	AC	3 ms 5,416 KB
testcase_48	AC	3 ms 5,424 KB
testcase_49	AC	3 ms 5,584 KB
testcase_50	AC	3 ms 5,408 KB
testcase_51	AC	3 ms 5,464 KB
testcase_52	AC	3 ms 5,416 KB
testcase_53	AC	3 ms 5,416 KB
testcase_54	AC	3 ms 5,392 KB
testcase_55	AC	30 ms 9,452 KB
testcase_56	AC	60 ms 13,536 KB
testcase_57	AC	56 ms 10,452 KB
testcase_58	AC	25 ms 7,336 KB
testcase_59	AC	37 ms 9,516 KB
testcase_60	AC	24 ms 7,128 KB
testcase_61	AC	50 ms 10,104 KB
testcase_62	AC	53 ms 10,236 KB
testcase_63	AC	51 ms 10,036 KB
testcase_64	AC	29 ms 9,504 KB
testcase_65	AC	56 ms 10,232 KB
testcase_66	AC	56 ms 10,284 KB
testcase_67	AC	43 ms 9,684 KB
testcase_68	AC	37 ms 9,448 KB
testcase_69	AC	50 ms 9,996 KB
testcase_70	AC	74 ms 9,832 KB
testcase_71	AC	42 ms 7,372 KB
testcase_72	AC	90 ms 10,252 KB
testcase_73	AC	87 ms 10,036 KB
testcase_74	AC	53 ms 9,436 KB
testcase_75	AC	85 ms 10,096 KB
testcase_76	AC	61 ms 9,500 KB
testcase_77	AC	43 ms 7,448 KB
testcase_78	AC	47 ms 9,468 KB
testcase_79	AC	38 ms 7,156 KB
testcase_80	AC	85 ms 10,424 KB
testcase_81	AC	85 ms 10,040 KB
testcase_82	AC	62 ms 9,688 KB
testcase_83	AC	67 ms 9,632 KB
testcase_84	AC	57 ms 9,628 KB
testcase_85	AC	8 ms 5,756 KB
testcase_86	AC	57 ms 9,556 KB
testcase_87	AC	74 ms 9,944 KB
testcase_88	AC	32 ms 7,004 KB
testcase_89	AC	67 ms 9,540 KB
testcase_90	AC	32 ms 6,784 KB
testcase_91	AC	72 ms 9,624 KB

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

ソースコード

raw source code

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <deque>
using namespace std;

#define Inf 1e15
#define maxn 300010

long long d[maxn];
long long dp[maxn][2]; // dp[i][0]: sleep at i day, dp[i][1]: read at i day

struct line { // y = mx + b
	long long m; // slope
	long long b; // intercept
	line(long long m, long long b): m(m), b(b) {}
};

long long foo(line l, long long i, long long a, long long b) { // return dp[i][1] from line l(j)
	return l.m * i + l.b + b * i * (i + 1) / 2 - a * i;
}

double vertex(line l1, line l2) { // the intersection of l1 and l2
	return 1.0 * (l2.b - l1.b) / (l1.m - l2.m);
}

// reamin: w
// days: n
// study 1 day: -a
// study for x days: + x * b
// sleep in i day: + d[i]

int main() {
	long long n, a, b, w;
	cin >> n >> a >> b >> w;
	for (int i = 1; i <= n; i++)
		cin >> d[i];
	dp[0][0] = dp[0][1] = w;
	deque<line> dq;
	dq.push_front(line(0, w)); // sine dp[j][0] = w
	for (long long i = 1; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + d[i]; // sleep
		// consider the value of dp[i][1] by subtituting i into dq[0]
		while (dq.size() > 1 && (foo(dq[1], i, a, b) < foo(dq[0], i, a, b)))
			dq.pop_front(); // we no longer need dq[0], pop out
		dp[i][1] = foo(dq[0], i, a, b);
		// cout << dp[i][0] << " " << dp[i][1] << " " << dq.size() << '\n';
		// add line "i" into dq
		line tmp = line(0, 0);
		tmp.m = -1 * i * b; // since this line will be treat as j in the future, the slope's j = i now
		tmp.b = dp[i][0] + b * i * (i - 1) / 2 + i * a;
		while (dq.size() >= 2 && (vertex(dq[dq.size() - 1], dq[dq.size() - 2]) > vertex(tmp, dq[dq.size() - 2])))
			dq.pop_back();
		dq.push_back(tmp);
	}
	cout << min(dp[n][1], dp[n][0]) << '\n';
	return 0;
}

yukicoder

結果

テストケース

ソースコード