結果

問題 No.409 ダイエット
ユーザー monnu
提出日時 2021-02-20 02:11:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,548 bytes
コンパイル時間 1,767 ms
コンパイル使用メモリ 175,480 KB
実行使用メモリ 7,808 KB
最終ジャッジ日時 2024-09-17 05:22:28
合計ジャッジ時間 7,782 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 83
権限があれば一括ダウンロードができます

ソースコード

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