結果

問題 No.595 登山
ユーザー ryoissyryoissy
提出日時 2017-11-10 23:25:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 469 ms / 1,500 ms
コード長 1,547 bytes
コンパイル時間 1,660 ms
コンパイル使用メモリ 166,972 KB
実行使用メモリ 27,008 KB
最終ジャッジ日時 2024-05-03 14:39:11
合計ジャッジ時間 10,924 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
16,128 KB
testcase_01 AC 7 ms
16,000 KB
testcase_02 AC 7 ms
16,128 KB
testcase_03 AC 7 ms
16,000 KB
testcase_04 AC 441 ms
26,624 KB
testcase_05 AC 134 ms
19,200 KB
testcase_06 AC 379 ms
24,960 KB
testcase_07 AC 48 ms
16,896 KB
testcase_08 AC 71 ms
17,664 KB
testcase_09 AC 392 ms
25,216 KB
testcase_10 AC 271 ms
22,400 KB
testcase_11 AC 241 ms
21,632 KB
testcase_12 AC 42 ms
16,896 KB
testcase_13 AC 105 ms
18,688 KB
testcase_14 AC 452 ms
26,752 KB
testcase_15 AC 454 ms
27,008 KB
testcase_16 AC 457 ms
26,880 KB
testcase_17 AC 458 ms
26,752 KB
testcase_18 AC 454 ms
27,008 KB
testcase_19 AC 463 ms
26,880 KB
testcase_20 AC 461 ms
27,008 KB
testcase_21 AC 466 ms
26,880 KB
testcase_22 AC 469 ms
27,008 KB
testcase_23 AC 469 ms
26,752 KB
testcase_24 AC 7 ms
16,128 KB
testcase_25 AC 6 ms
16,000 KB
testcase_26 AC 469 ms
26,880 KB
testcase_27 AC 462 ms
27,008 KB
testcase_28 AC 458 ms
26,880 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |         scanf("%d%lld",&n,&p);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:63:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |                 scanf("%lld",&h[i]);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define INF 100000000000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class segtree{
public:
	static const int N=1<<18;
	ll dp[1<<19];
	ll lazy[1<<19];
	segtree(){
		memset(dp,0,sizeof(dp));
	}
	void lazy_eval(int k){
		dp[k]+=lazy[k];
		if(k<N-1){
			lazy[k*2+1]+=lazy[k];
			lazy[k*2+2]+=lazy[k];
		}
		lazy[k]=0;
	}
	void lazy_upd(int k){
		dp[k]=min(dp[k*2+1],dp[k*2+2]);
	}

	void update(int a,int b,ll v,int k=0,int l=0,int r=N){
		lazy_eval(k);
		if(b<=l || r<=a)return;
		if(a<=l && r<=b){
			lazy[k]+=v;
			lazy_eval(k);
			return;
		}
		int mid=(l+r)/2;
		update(a,b,v,k*2+1,l,mid);
		update(a,b,v,k*2+2,mid,r);
		lazy_upd(k);
	}

	ll query(int a,int b,int k=0,int l=0,int r=N){
		lazy_eval(k);
		if(b<=l || r<=a)return INF;
		if(a<=l && r<=b)return dp[k];
		int mid=(l+r)/2;
		ll vl=query(a,b,k*2+1,l,mid);
		ll vr=query(a,b,k*2+2,mid,r);
		lazy_upd(k);
		return min(vl,vr);
	}
};

segtree seg[3];

int n;
ll p;
ll h[200005];


int main(void){
	scanf("%d%lld",&n,&p);
	for(int i=0;i<n;i++){
		scanf("%lld",&h[i]);
	}
	for(int i=1;i<n;i++){
		ll val=h[i]-h[i-1];
		if(val>0){
			seg[0].update(0,i,val);
			seg[2].update(0,i-1,val);
		}else{
			seg[1].update(0,i-1,-val);
		}
		ll bv=seg[0].query(0,i);
		bv=min(bv,seg[2].query(0,i)+p);
		seg[1].update(i,i+1,min(seg[1].query(0,i)+p,bv));
		seg[2].update(i,i+1,min(seg[1].query(0,i)+p,bv));
		seg[0].update(i,i+1,bv);
	}
	ll ans=INF;
	for(int i=0;i<3;i++){
		ans=min(ans,seg[i].query(n-1,n));
	}
	printf("%lld\n",ans);
	return 0;
}
0