結果

問題 No.595 登山
ユーザー Naoyk1212
提出日時 2017-11-11 01:39:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 794 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 64,320 KB
実行使用メモリ 814,776 KB
最終ジャッジ日時 2024-11-24 16:32:13
合計ジャッジ時間 43,607 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 4
other MLE * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
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];
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, inf);
	dp[0][0] = 0;
	dp[0][1] = p;

	// 0: ->
	// 1: <-

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

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