結果
問題 | No.409 ダイエット |
ユーザー | okaduki |
提出日時 | 2018-02-28 03:12:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,378 bytes |
コンパイル時間 | 1,740 ms |
コンパイル使用メモリ | 175,016 KB |
実行使用メモリ | 31,544 KB |
最終ジャッジ日時 | 2023-09-07 18:37:13 |
合計ジャッジ時間 | 12,901 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,384 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,384 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 1 ms
4,384 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 1 ms
4,384 KB |
testcase_17 | AC | 2 ms
4,384 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 1 ms
4,380 KB |
testcase_21 | AC | 1 ms
4,380 KB |
testcase_22 | AC | 2 ms
4,384 KB |
testcase_23 | AC | 1 ms
4,380 KB |
testcase_24 | AC | 1 ms
4,380 KB |
testcase_25 | AC | 2 ms
4,384 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,384 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 1 ms
4,384 KB |
testcase_30 | AC | 2 ms
4,380 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 2 ms
4,384 KB |
testcase_33 | AC | 2 ms
4,380 KB |
testcase_34 | AC | 2 ms
4,380 KB |
testcase_35 | AC | 3 ms
4,384 KB |
testcase_36 | AC | 3 ms
4,384 KB |
testcase_37 | AC | 3 ms
4,384 KB |
testcase_38 | AC | 3 ms
4,380 KB |
testcase_39 | AC | 3 ms
4,384 KB |
testcase_40 | AC | 2 ms
4,384 KB |
testcase_41 | AC | 3 ms
4,380 KB |
testcase_42 | AC | 3 ms
4,380 KB |
testcase_43 | AC | 3 ms
4,384 KB |
testcase_44 | AC | 3 ms
4,384 KB |
testcase_45 | AC | 3 ms
4,380 KB |
testcase_46 | AC | 3 ms
4,384 KB |
testcase_47 | AC | 3 ms
4,380 KB |
testcase_48 | AC | 3 ms
4,380 KB |
testcase_49 | AC | 4 ms
4,384 KB |
testcase_50 | AC | 3 ms
4,384 KB |
testcase_51 | AC | 3 ms
4,384 KB |
testcase_52 | AC | 4 ms
4,380 KB |
testcase_53 | AC | 3 ms
4,384 KB |
testcase_54 | AC | 3 ms
4,384 KB |
testcase_55 | AC | 149 ms
15,464 KB |
testcase_56 | AC | 59 ms
7,496 KB |
testcase_57 | AC | 375 ms
31,544 KB |
testcase_58 | AC | 135 ms
15,232 KB |
testcase_59 | AC | 161 ms
14,596 KB |
testcase_60 | AC | 113 ms
13,640 KB |
testcase_61 | AC | 303 ms
26,212 KB |
testcase_62 | AC | 372 ms
31,228 KB |
testcase_63 | AC | 282 ms
24,228 KB |
testcase_64 | AC | 125 ms
13,664 KB |
testcase_65 | AC | 235 ms
17,040 KB |
testcase_66 | AC | 319 ms
26,868 KB |
testcase_67 | AC | 259 ms
23,584 KB |
testcase_68 | AC | 163 ms
14,704 KB |
testcase_69 | AC | 265 ms
22,856 KB |
testcase_70 | AC | 270 ms
24,368 KB |
testcase_71 | AC | 148 ms
15,668 KB |
testcase_72 | AC | 367 ms
31,072 KB |
testcase_73 | AC | 268 ms
20,188 KB |
testcase_74 | AC | 203 ms
20,008 KB |
testcase_75 | AC | 286 ms
22,908 KB |
testcase_76 | AC | 247 ms
22,308 KB |
testcase_77 | AC | 108 ms
10,664 KB |
testcase_78 | AC | 189 ms
18,532 KB |
testcase_79 | AC | 117 ms
13,140 KB |
testcase_80 | AC | 355 ms
29,388 KB |
testcase_81 | AC | 277 ms
21,268 KB |
testcase_82 | AC | 224 ms
21,060 KB |
testcase_83 | AC | 234 ms
21,156 KB |
testcase_84 | AC | 154 ms
13,092 KB |
testcase_85 | WA | - |
testcase_86 | WA | - |
testcase_87 | AC | 288 ms
25,392 KB |
testcase_88 | AC | 82 ms
9,544 KB |
testcase_89 | AC | 130 ms
8,752 KB |
testcase_90 | AC | 58 ms
6,616 KB |
testcase_91 | AC | 138 ms
9,188 KB |
ソースコード
// 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; }