結果

問題 No.595 登山
ユーザー Naoyk1212
提出日時 2017-11-11 00:33:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 1,152 bytes
コンパイル時間 509 ms
コンパイル使用メモリ 64,188 KB
実行使用メモリ 816,444 KB
最終ジャッジ日時 2024-11-24 16:11:20
合計ジャッジ時間 43,957 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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][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