結果

問題 No.595 登山
ユーザー vjudge1
提出日時 2025-08-23 16:03:20
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 1,500 ms
コード長 805 bytes
コンパイル時間 2,588 ms
コンパイル使用メモリ 171,344 KB
実行使用メモリ 11,412 KB
最終ジャッジ日時 2025-08-23 16:03:25
合計ジャッジ時間 4,642 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
int n,p,h[N],dp[N][2],sum[N],sum2[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> p;
	for(int i = 1;i <= n;i++)cin >> h[i];
	for(int i = 2;i <= n;i++)sum[i] = sum[i - 1] + min(p,max(0ll,h[i] - h[i - 1]));
	for(int i = 2;i <= n;i++)sum2[i] = sum2[i - 1] + min(p,max(0ll,h[i - 1] - h[i]));
	dp[2][0] = sum[2];
	dp[2][1] = 1e17;
	int minn = -sum2[2];
	for(int i = 3;i <= n;i++){
		dp[i][0] = sum[i];
		dp[i][1] = min(sum2[i - 1] + minn + p + (i == n) * min(p,max(0ll,h[i - 1] - h[i])),dp[i - 1][1] + min(p,max(0ll,h[i] - h[i - 1])) + (i == n) * p);
		minn = min({minn,dp[i - 1][0] - sum2[i],dp[i - 1][1] + p - sum2[i]});
	}
	cout << min(dp[n][0],dp[n][1]);
}
0