結果

問題 No.409 ダイエット
ユーザー monnumonnu
提出日時 2021-02-20 02:11:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,548 bytes
コンパイル時間 1,710 ms
コンパイル使用メモリ 174,832 KB
実行使用メモリ 7,812 KB
最終ジャッジ日時 2023-10-17 06:44:45
合計ジャッジ時間 9,578 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 2 ms
4,348 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
4,348 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 2 ms
4,348 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 AC 59 ms
7,812 KB
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 WA -
testcase_83 WA -
testcase_84 WA -
testcase_85 WA -
testcase_86 WA -
testcase_87 WA -
testcase_88 WA -
testcase_89 WA -
testcase_90 WA -
testcase_91 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 1000000007
#define INF 1000000000000000000
#define MAX 1000000

//傾きが単調減少、xが単調増加
template<class T>
class CHT{
  struct Line{
    T a,b;
    Line(ll a_,ll b_):a(a_),b(b_){}
    Line():a(0),b(0){}
    T get(T x){
      return a*x+b;
    }
  };
private:
  deque<Line> deq;
  bool check(Line &l1,Line &l2,Line &l3) const{
    return (l2.a-l1.a)*(l3.b-l2.b)<(l2.b-l1.b)*(l3.a-l2.a);
  }
public:
  CHT(){}
  void insert(T a,T b){
    Line l3(a,b);
    while(deq.size()>=2){
      Line l2=*deq.rbegin();
      Line l1=*(deq.rbegin()-1);
      if(check(l1,l2,l3)){
        break;
      }
      deq.pop_back();
    }
    deq.push_back(l3);
  }
  T get(T x){
    while(deq.size()>=2){
      Line l1=*begin(deq);
      Line l2=*(begin(deq)+1);
      if(l1.get(x)<l2.get(x)){
        break;
      }
      deq.pop_front();
    }
    Line l=*begin(deq);
    return l.get(x);
  }
};

int main(){
  ll N;
  ll A,B,W;
  cin>>N>>A>>B>>W;
  vector<ll> D(N);
  for(int i=0;i<N;i++){
    cin>>D[i];
  }
  vector<ll> dp(N+1,INF);
  dp[0]=W;
  CHT<ll> cht;
  cht.insert(0,dp[0]);
  for(ll i=0;i<N;i++){
    dp[i+1]=-(i+1)*A+(i+1)*i*B/2+cht.get(i+1)+D[i]+A;
    cht.insert(-(i+1)*B,(i+2)*(i+1)*B/2+(i+1)*A+dp[i+1]+D[i]);
  }

  ll ans=INF;
  for(ll i=0;i<=N;i++){
    //cout<<dp[i]<<" ";
    ans=min<ll>(ans,dp[i]+(N-i)*(N-i+1)*B/2-(N-i)*A);
  }
  //cout<<endl;
  cout<<ans<<endl;
}
0