結果

問題 No.595 登山
ユーザー ryoissy
提出日時 2017-11-10 23:25:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 743 ms / 1,500 ms
コード長 1,547 bytes
コンパイル時間 3,412 ms
コンパイル使用メモリ 166,440 KB
実行使用メモリ 29,412 KB
最終ジャッジ日時 2024-11-24 15:34:37
合計ジャッジ時間 14,977 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0