結果
問題 | No.595 登山 |
ユーザー | HIR180 |
提出日時 | 2017-11-10 22:58:55 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 30 ms / 1,500 ms |
コード長 | 1,033 bytes |
コンパイル時間 | 1,390 ms |
コンパイル使用メモリ | 144,000 KB |
実行使用メモリ | 7,604 KB |
最終ジャッジ日時 | 2023-08-16 03:38:01 |
合計ジャッジ時間 | 2,965 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,532 KB |
testcase_01 | AC | 3 ms
6,820 KB |
testcase_02 | AC | 4 ms
6,516 KB |
testcase_03 | AC | 4 ms
6,532 KB |
testcase_04 | AC | 22 ms
7,564 KB |
testcase_05 | AC | 9 ms
6,732 KB |
testcase_06 | AC | 21 ms
7,192 KB |
testcase_07 | AC | 5 ms
6,584 KB |
testcase_08 | AC | 7 ms
6,644 KB |
testcase_09 | AC | 21 ms
7,264 KB |
testcase_10 | AC | 16 ms
7,104 KB |
testcase_11 | AC | 14 ms
6,944 KB |
testcase_12 | AC | 4 ms
6,600 KB |
testcase_13 | AC | 8 ms
6,752 KB |
testcase_14 | AC | 19 ms
7,600 KB |
testcase_15 | AC | 19 ms
7,416 KB |
testcase_16 | AC | 19 ms
7,344 KB |
testcase_17 | AC | 20 ms
7,340 KB |
testcase_18 | AC | 20 ms
7,324 KB |
testcase_19 | AC | 29 ms
7,356 KB |
testcase_20 | AC | 30 ms
7,372 KB |
testcase_21 | AC | 29 ms
7,396 KB |
testcase_22 | AC | 29 ms
7,332 KB |
testcase_23 | AC | 30 ms
7,444 KB |
testcase_24 | AC | 3 ms
6,516 KB |
testcase_25 | AC | 3 ms
6,612 KB |
testcase_26 | AC | 29 ms
7,604 KB |
testcase_27 | AC | 22 ms
7,324 KB |
testcase_28 | AC | 22 ms
7,384 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define mod 1000000007 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) int n,p,h[200005]; ll dp[200005][2]; int main(){ scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",&h[i]); rep(i,200005) rep(j,2) dp[i][j] = 1e18; dp[1][0] = 0; for(int i=2;i<=n;i++){ dp[i][0] = min(dp[i-1][0]+min(1LL*p,max(0LL,1LL*h[i]-h[i-1])),dp[i-1][1]+max(0LL,1LL*h[i]-h[i-1])+1LL*p); dp[i][1] = min(dp[i-1][1]+min(1LL*p,max(0LL,1LL*h[i-1]-h[i])),dp[i-1][0]+max(0LL,1LL*h[i-1]-h[i])+1LL*p); } cout<<min(dp[n][0],dp[n][1])<<endl; }