#651492 (C++17) No.409 ダイエット

提出ソース

結果

問題	No.409 ダイエット
ユーザー	cumin
提出日時	2021-04-26 00:11:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	108 ms / 2,000 ms
コード長	4,753 bytes
コンパイル時間	3,403 ms
コンパイル使用メモリ	224,640 KB
実行使用メモリ	30,400 KB
最終ジャッジ日時	2023-09-17 14:18:06
合計ジャッジ時間	10,499 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	2 ms 4,384 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	1 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	1 ms 4,380 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	1 ms 4,380 KB
testcase_20	AC	1 ms 4,376 KB
testcase_21	AC	1 ms 4,376 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	1 ms 4,384 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	2 ms 4,380 KB
testcase_28	AC	1 ms 4,380 KB
testcase_29	AC	1 ms 4,376 KB
testcase_30	AC	2 ms 4,376 KB
testcase_31	AC	1 ms 4,380 KB
testcase_32	AC	2 ms 4,376 KB
testcase_33	AC	2 ms 4,376 KB
testcase_34	AC	1 ms 4,376 KB
testcase_35	AC	2 ms 4,380 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	3 ms 4,376 KB
testcase_38	AC	2 ms 4,380 KB
testcase_39	AC	2 ms 4,380 KB
testcase_40	AC	2 ms 4,376 KB
testcase_41	AC	3 ms 4,380 KB
testcase_42	AC	3 ms 4,380 KB
testcase_43	AC	3 ms 4,380 KB
testcase_44	AC	3 ms 4,380 KB
testcase_45	AC	3 ms 4,380 KB
testcase_46	AC	3 ms 4,376 KB
testcase_47	AC	3 ms 4,376 KB
testcase_48	AC	3 ms 4,380 KB
testcase_49	AC	3 ms 4,380 KB
testcase_50	AC	2 ms 4,380 KB
testcase_51	AC	3 ms 4,376 KB
testcase_52	AC	3 ms 4,376 KB
testcase_53	AC	3 ms 4,376 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	50 ms 16,600 KB
testcase_56	AC	60 ms 29,980 KB
testcase_57	AC	100 ms 30,400 KB
testcase_58	AC	41 ms 11,144 KB
testcase_59	AC	59 ms 17,708 KB
testcase_60	AC	38 ms 10,808 KB
testcase_61	AC	85 ms 20,424 KB
testcase_62	AC	96 ms 30,136 KB
testcase_63	AC	82 ms 19,252 KB
testcase_64	AC	47 ms 16,404 KB
testcase_65	AC	87 ms 29,600 KB
testcase_66	AC	98 ms 30,156 KB
testcase_67	AC	72 ms 18,764 KB
testcase_68	AC	58 ms 17,364 KB
testcase_69	AC	81 ms 19,740 KB
testcase_70	AC	83 ms 18,936 KB
testcase_71	AC	47 ms 11,212 KB
testcase_72	AC	108 ms 30,188 KB
testcase_73	AC	92 ms 20,544 KB
testcase_74	AC	62 ms 17,164 KB
testcase_75	AC	100 ms 29,760 KB
testcase_76	AC	70 ms 17,804 KB
testcase_77	AC	45 ms 11,072 KB
testcase_78	AC	56 ms 16,668 KB
testcase_79	AC	42 ms 10,916 KB
testcase_80	AC	103 ms 29,820 KB
testcase_81	AC	92 ms 19,936 KB
testcase_82	AC	71 ms 17,772 KB
testcase_83	AC	76 ms 18,188 KB
testcase_84	AC	62 ms 17,224 KB
testcase_85	AC	9 ms 4,808 KB
testcase_86	AC	61 ms 17,128 KB
testcase_87	AC	86 ms 18,796 KB
testcase_88	AC	34 ms 10,212 KB
testcase_89	AC	66 ms 17,972 KB
testcase_90	AC	32 ms 10,368 KB
testcase_91	AC	69 ms 18,164 KB

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

ソースコード

raw source code

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using Bint = boost::multiprecision::cpp_int;
//#include <atcoder/all>

#define ll long long
#define ld long double

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep2(i, a, b) for(int i = a; i <= b; ++i)
#define rrep(i, a, b) for(int i = a; i >= b; --i)

#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define pld pair<ld,ld>

#define fi first
#define se second

#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define vd vector<double>
#define vll vector<ll>
#define vld vector<ld>
#define vpii vector<pii>
#define vpdd vector<pdd>
#define vpll vector<pll>
#define vpld vector<pld>
#define vvi(a,b,c,d) vector<vector<int>> a(b,vector<int>(c,d));
#define vvll(a,b,c,d) vector<vector<ll>> a(b,vector<ll>(c,d));

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define MAX(x) *max_element(all(x)) 
#define MIN(x) *min_element(all(x)) 
#define sz(a) ((ll)(a).size())

#define endl '\n'
using namespace std;
//using namespace atcoder;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> //切り捨て
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) { //切り上げ
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}
const ll INF=1e18+1;
const int inf=1e9+1;
const double PI=acos(-1);
int dy[8] = {0,1,0,-1,-1,1,1,-1};
int dx[8] = {1,0,-1,0,1,1,-1,-1};

bool range(int y, int x, int h, int w){
  if(y < 0 || x < 0 || y >= h || x >= w) return false;
  else return true;
}

//const int MOD=1000000007;
//using mint = modint1000000007;
//const int MOD=998244353;
//using mint = modint998244353;

const int M = 500001;
using Graph = vector<vector<int>>;

// LiChaoTree
// 直線追加，N個の座標x（昇順）における最小値
// verify: https://judge.yosupo.jp/submission/45842

template<typename T> struct LiChaoTree {
  const T INF = numeric_limits< T >::max() / 2;
  struct Line {
    T a, b;
    Line(T a, T b) : a(a), b(b) {}
    T eval(T x) { return a*x + b; }
  };
  
  int n; //座標の数
  vector< Line > data; //直線群
  vector< T > pos; //i番目の座標x_i
  LiChaoTree(int n) {
    pos.resize(n);
    iota(pos.begin(), pos.end(), 0); //座標圧縮
    init(n);
  }
  LiChaoTree(const vector< T > &pos) : pos(pos) { init(pos.size()); }
  
  void init(int n_){ //2べきにしてる
    n = 1;
    while(n < n_) n <<= 1;
    while((int)pos.size() < n) pos.emplace_back(pos.back() + 1);
    data.assign(n << 1, Line(0, INF));
  }
  
  void add_line(T a, T b){
    Line x(a, b);
    update(1, 0, n-1, x); //[0, n-1]でupdate
  }
  
  inline bool over(Line &a, Line &b, T lb, T ub){
    return a.eval(lb) >= b.eval(lb) && a.eval(ub) >= b.eval(ub); //[lb, ub]で直線aが直線bの上にある
  }
  
  void update(int k, int l, int r, Line &x){
    T lb = pos[l], ub = pos[r];
    if(over(x, data[k], lb, ub)) return;  //加えたいのが完全に上ならなんもしない
    if(over(data[k], x, lb, ub)) {        //加えたいのが完全に下なら変える
      data[k] = x;
      return;
    }
    int c = (l+r) >> 1;
    if(x.eval(pos[c]) < data[k].eval(pos[c])) swap(x, data[k]); //中点で加えたい線が下に来るならswap
    if(x.eval(lb) <= data[k].eval(lb)) update(k << 1|0, l, c, x); //https://smijake3.hatenablog.com/entry/2018/06/16/144548のNo.3
    else update(k << 1|1, c+1, r, x); //https://smijake3.hatenablog.com/entry/2018/06/16/144548のNo.4
  }
  
  T get_min(ll x) { //座標xを含む区間の最小値を計算（子から親へ）
    int i = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
    T res = INF;
    int k = i + n;
    while(k > 0){
      res = min(res, data[k].eval(pos[i]));
      k >>= 1;
    }
    return res;
  }
};
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  cout << fixed << setprecision(15);
  
  ll n, a, b, w;
  cin >> n >> a >> b >> w;
  vll d(n);
  rep(i, n) cin >> d[i];
  vll dp(n+1);
  dp[0] = 0;
  
  vll day(n+1);
  rep(i, n+1) day[i] = (ll)i;
  
  LiChaoTree<ll> LCT(day);
  LCT.add_line(0, 0);
  rep2(i, 1, n){
    dp[i] = LCT.get_min(i) - (ll)a*(i-1) + (ll)((ll)i*i-i)*b/2 + d[i-1];
    LCT.add_line(-(ll)i*b, dp[i] + (ll)i*a + (ll)((ll)i*i+i)*b/2);
  }
  ll ans = INF;
  rep(i, n+1){
    chmin(ans, w + dp[i] - (n-i)*a + ((ll)(n-i)*(n-i+1)/2)*(ll)b);
  }
  cout << ans << endl;
  return 0;
}

yukicoder

結果

テストケース

ソースコード