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

提出ソース

結果

問題	No.409 ダイエット
ユーザー	okaduki
提出日時	2018-02-28 03:12:08
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	3 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	2 ms 6,944 KB
testcase_35	AC	3 ms 6,940 KB
testcase_36	AC	4 ms 6,940 KB
testcase_37	AC	3 ms 6,944 KB
testcase_38	AC	4 ms 6,940 KB
testcase_39	AC	3 ms 6,940 KB
testcase_40	AC	4 ms 6,940 KB
testcase_41	AC	3 ms 6,944 KB
testcase_42	AC	4 ms 6,940 KB
testcase_43	AC	3 ms 6,940 KB
testcase_44	AC	3 ms 6,940 KB
testcase_45	AC	4 ms 6,940 KB
testcase_46	AC	4 ms 6,944 KB
testcase_47	AC	3 ms 6,944 KB
testcase_48	AC	3 ms 6,940 KB
testcase_49	AC	4 ms 6,940 KB
testcase_50	AC	3 ms 6,940 KB
testcase_51	AC	4 ms 6,944 KB
testcase_52	AC	3 ms 6,944 KB
testcase_53	AC	3 ms 6,940 KB
testcase_54	AC	3 ms 6,940 KB
testcase_55	AC	147 ms 15,744 KB
testcase_56	AC	58 ms 7,552 KB
testcase_57	AC	373 ms 31,616 KB
testcase_58	AC	135 ms 15,232 KB
testcase_59	AC	161 ms 14,976 KB
testcase_60	AC	114 ms 13,696 KB
testcase_61	AC	303 ms 26,496 KB
testcase_62	AC	369 ms 31,360 KB
testcase_63	AC	281 ms 24,320 KB
testcase_64	AC	126 ms 13,824 KB
testcase_65	AC	240 ms 17,152 KB
testcase_66	AC	318 ms 27,008 KB
testcase_67	AC	250 ms 23,808 KB
testcase_68	AC	161 ms 14,848 KB
testcase_69	AC	267 ms 22,912 KB
testcase_70	AC	269 ms 24,704 KB
testcase_71	AC	149 ms 15,872 KB
testcase_72	AC	372 ms 31,096 KB
testcase_73	AC	264 ms 20,352 KB
testcase_74	AC	209 ms 20,096 KB
testcase_75	AC	286 ms 22,912 KB
testcase_76	AC	253 ms 22,528 KB
testcase_77	AC	109 ms 10,752 KB
testcase_78	AC	184 ms 18,816 KB
testcase_79	AC	117 ms 13,312 KB
testcase_80	AC	347 ms 29,568 KB
testcase_81	AC	274 ms 21,504 KB
testcase_82	AC	230 ms 21,248 KB
testcase_83	AC	239 ms 21,376 KB
testcase_84	AC	153 ms 13,184 KB
testcase_85	WA	-
testcase_86	WA	-
testcase_87	AC	293 ms 25,728 KB
testcase_88	AC	81 ms 9,984 KB
testcase_89	AC	130 ms 8,832 KB
testcase_90	AC	58 ms 6,940 KB
testcase_91	AC	137 ms 9,344 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 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;
}

yukicoder

結果

テストケース

ソースコード