結果

問題 No.595 登山
ユーザー Naoyk1212Naoyk1212
提出日時 2017-11-11 00:33:04
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 1,152 bytes
コンパイル時間 539 ms
コンパイル使用メモリ 64,200 KB
実行使用メモリ 816,364 KB
最終ジャッジ日時 2024-05-03 15:04:28
合計ジャッジ時間 4,337 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int to(long long int&, long long int)’:
main.cpp:12:1: warning: no return statement in function returning non-void [-Wreturn-type]
   12 | }
      | ^

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<stack>
#include <algorithm>


long long dp[200001][2][2];
const long long inf = 1e18;

long long to(long long &x, long long y) {
	x = std::min(x, y);
}

int main(){
	int n, p;
	std::cin >> n >> p;
	
	std::vector<int> h(n);
	for (int i = 0; i < n; i++) {
		std::cin >> h[i];
	}

	std::fill_n(**dp, 200001 * 2 * 2, inf);
	dp[0][0][0] = 0;
	
	for (int i = 0; i < n; i++) {
		to(dp[i + 1][0][0], dp[i][0][0] + std::max(0, h[i + 1] - h[i]));
		if (h[i] <= h[i + 1]) {
			to(dp[i + 1][0][1], dp[i][0][0] + p);
		}
		if (h[i] >= h[i + 1]) {
			to(dp[i + 1][1][0], dp[i][0][0] + p);
		}

		to(dp[i + 1][0][0], dp[i][1][0] + std::max(0, h[i + 1] - h[i]));
		if (h[i] <= h[i + 1]) {
			to(dp[i + 1][1][0], dp[i][1][0] + 0);
		}
		if (h[i] >= h[i + 1]) {
			to(dp[i + 1][0][1], dp[i][1][0] + p);
		}

		to(dp[i + 1][0][0], dp[i][0][1] + std::max(0, h[i + 1] - h[i]));
		if (h[i] <= h[i + 1]) {
			to(dp[i + 1][1][0], dp[i][0][1] + p);
		}
		if (h[i] >= h[i + 1]) {
			to(dp[i + 1][0][1], dp[i][0][1] + 0);
		}
	}

	long long ans = std::min({dp[n][0][0], dp[n][1][0], dp[n][0][1]});
	std::cout << ans << std::endl;
}
0