#239768 (C++14) No.409 ダイエット

• 問題: No.409 ダイエット
• ユーザー: okaduki
• 提出日時: 2018-02-28 03:12:08
• 言語: C++14 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 3,378 bytes
• コンパイル時間: 2,546 ms
• コンパイル使用メモリ: 177,656 KB
• 実行使用メモリ: 31,616 KB
• 最終ジャッジ日時: 2024-06-25 12:21:40
• 合計ジャッジ時間: 12,046 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 90 WA * 2

ソースコード

// This code is very suspicious

#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 4e18;


template<class T, class Comp=greater<T>>
struct Line{
  static const T NaN = numeric_limits<T>::max();

  T a, b;
  Line(T a_=0, T b_=0) : a(a_), b(b_) {}
  mutable function<const Line*()> next;
  bool operator<(const Line& rhs) const {
	if(rhs.b != NaN) return Comp()(a, rhs.a);
	const Line* nxt = next();
	
	return Comp()(a * rhs.a + b, nxt->a * rhs.a + nxt->b);
  }
};

template<class T, class Comp=greater<T>>
struct ConvexHullTrick{
  using LineT = Line<T,Comp>;
  multiset<LineT> lines;
  
  ConvexHullTrick(){
  }

  bool bad(typename multiset<LineT>::iterator it){
	auto nxt = next(it);
	if(it == begin(lines)){
	  if(nxt == end(lines))
		return false;
	  return it->a == nxt->a && Comp()(nxt->b, it->b);
	}
	auto prv = prev(it);

	if(nxt == end(lines))
	  return prv->a == it->a && Comp()(nxt->b, it->b);

	return Comp()(-(double)(prv->a - it->a)*(nxt->b - it->b),
				-(double)(nxt->a - it->a)*(prv->b - it->b));
  }

  // y = ax + b
  void add(T a, T b){
	auto it = lines.emplace(a, b);
	if(bad(it)){
	  lines.erase(it);
	  return;
	}
	it->next = [=](){ return &*next(it); };
	auto tmp = next(it);
	while(tmp != end(lines) && bad(tmp)) tmp = lines.erase(tmp);
	--tmp;
	while(tmp != begin(lines)){
	  --tmp;
	  if(!bad(tmp)) break;
	  tmp = lines.erase(tmp);
	}
  }

  T f(const LineT& l, T x){
	return l.a * x + l.b;
  }

  T getmin(T x){
	auto it = lines.lower_bound(LineT(x, LineT::NaN));
	return f(*it, x);
  }
};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  LL N, A, B, W;
  cin >> N >> A >> B >> W;

  VL ds(N+1);
  REP(i,N) cin >> ds[i+1];

  VL dp(N+1, INF);
  ConvexHullTrick<LL> cht;

  LL ans = N*(N+1)/2*B - N*A;
  for(LL i=1;i<=N;++i){
	dp[i] = i * (i-1) / 2 * B - (i-1)*A + ds[i];
	if(i>1)
	  mini(dp[i], ds[i] - (i-1)*A + (i*i-i)/2*B + cht.getmin(i));

	cht.add(-B * i, dp[i] + i*A + i*(i+1)/2*B);
	mini(ans, dp[i] + (N-i)*(N-i+1)/2*B - (N-i)*A);
  }

  cout << ans+W << endl;

  return 0;
}