結果
問題 | No.409 ダイエット |
ユーザー | Yang33 |
提出日時 | 2018-01-22 15:53:03 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,915 ms / 2,000 ms |
コード長 | 4,338 bytes |
コンパイル時間 | 2,300 ms |
コンパイル使用メモリ | 181,000 KB |
実行使用メモリ | 43,188 KB |
最終ジャッジ日時 | 2023-08-26 21:44:31 |
合計ジャッジ時間 | 54,880 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 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 | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,384 KB |
testcase_14 | AC | 1 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 1 ms
4,380 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 1 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,384 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 1 ms
4,380 KB |
testcase_24 | AC | 1 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,380 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,376 KB |
testcase_28 | AC | 1 ms
4,380 KB |
testcase_29 | AC | 1 ms
4,380 KB |
testcase_30 | AC | 1 ms
4,388 KB |
testcase_31 | AC | 2 ms
4,376 KB |
testcase_32 | AC | 2 ms
4,380 KB |
testcase_33 | AC | 1 ms
4,376 KB |
testcase_34 | AC | 1 ms
4,380 KB |
testcase_35 | AC | 16 ms
4,380 KB |
testcase_36 | AC | 17 ms
4,380 KB |
testcase_37 | AC | 17 ms
4,380 KB |
testcase_38 | AC | 17 ms
4,380 KB |
testcase_39 | AC | 17 ms
4,380 KB |
testcase_40 | AC | 17 ms
4,376 KB |
testcase_41 | AC | 19 ms
4,376 KB |
testcase_42 | AC | 19 ms
4,376 KB |
testcase_43 | AC | 16 ms
4,380 KB |
testcase_44 | AC | 15 ms
4,380 KB |
testcase_45 | AC | 18 ms
4,376 KB |
testcase_46 | AC | 17 ms
4,380 KB |
testcase_47 | AC | 17 ms
4,376 KB |
testcase_48 | AC | 16 ms
4,380 KB |
testcase_49 | AC | 17 ms
4,376 KB |
testcase_50 | AC | 17 ms
4,376 KB |
testcase_51 | AC | 17 ms
4,380 KB |
testcase_52 | AC | 18 ms
4,380 KB |
testcase_53 | AC | 17 ms
4,380 KB |
testcase_54 | AC | 15 ms
4,380 KB |
testcase_55 | AC | 880 ms
20,852 KB |
testcase_56 | AC | 1,387 ms
7,592 KB |
testcase_57 | AC | 1,915 ms
43,156 KB |
testcase_58 | AC | 757 ms
20,188 KB |
testcase_59 | AC | 1,183 ms
19,160 KB |
testcase_60 | AC | 690 ms
17,892 KB |
testcase_61 | AC | 1,696 ms
35,528 KB |
testcase_62 | AC | 1,806 ms
43,188 KB |
testcase_63 | AC | 1,617 ms
32,628 KB |
testcase_64 | AC | 824 ms
17,848 KB |
testcase_65 | AC | 1,646 ms
22,168 KB |
testcase_66 | AC | 1,868 ms
36,432 KB |
testcase_67 | AC | 1,395 ms
32,204 KB |
testcase_68 | AC | 1,124 ms
19,000 KB |
testcase_69 | AC | 1,568 ms
30,576 KB |
testcase_70 | AC | 1,519 ms
33,524 KB |
testcase_71 | AC | 822 ms
21,368 KB |
testcase_72 | AC | 1,902 ms
42,716 KB |
testcase_73 | AC | 1,639 ms
26,836 KB |
testcase_74 | AC | 1,046 ms
27,092 KB |
testcase_75 | AC | 1,677 ms
30,576 KB |
testcase_76 | AC | 1,243 ms
30,776 KB |
testcase_77 | AC | 759 ms
13,356 KB |
testcase_78 | AC | 937 ms
25,512 KB |
testcase_79 | AC | 728 ms
17,316 KB |
testcase_80 | AC | 1,793 ms
40,548 KB |
testcase_81 | AC | 1,708 ms
28,356 KB |
testcase_82 | AC | 1,238 ms
28,708 KB |
testcase_83 | AC | 1,306 ms
28,732 KB |
testcase_84 | AC | 1,032 ms
16,884 KB |
testcase_85 | AC | 109 ms
5,136 KB |
testcase_86 | AC | 1,044 ms
18,132 KB |
testcase_87 | AC | 1,535 ms
35,008 KB |
testcase_88 | AC | 558 ms
12,312 KB |
testcase_89 | AC | 1,143 ms
10,220 KB |
testcase_90 | AC | 518 ms
7,680 KB |
testcase_91 | AC | 1,229 ms
10,416 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using VS = vector<string>; using LL = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; using PLL = pair<LL, LL>; using VL = vector<LL>; using VVL = vector<VL>; #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, s, e) for (LL(i) = (s); (i) < (e); (i)++) #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--) #define debug(x) cerr << #x << ": " << x << endl const int INF = 1e9; const LL LINF = 1e16; const LL MOD = 1000000007; const double PI = acos(-1.0); int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 }; /* ----- 2018/01/22 Problem: yukicoder409 / Link: __CONTEST_URL__ ----- */ /* ------問題------ -----問題ここまで----- */ /* -----解説等----- ----解説ここまで---- */ struct CHT2{ typedef pair<LL,LL> PT; typedef LL RT; struct L{ LL a,b; L(LL a, LL b): a(a),b(b){} bool operator<(const L &rhs) const{ return a != rhs.a ? a > rhs.a : b < rhs.b; } }; struct CP{ LL n,d; L p; CP(LL _n,LL _d, const L &p):n(_n),d(_d),p(p){ if(d < 0) { n *= -1; d *= -1;} } bool operator<(const CP &rhs) const{ if(n == LINF || rhs.n == -LINF) return 0; if(n == -LINF || rhs.n == LINF) return 1; return n*rhs.d < rhs.n*d; } }; typedef set<L>::iterator It; set<L> S; set<CP> C; public: CHT2(){ // 番兵 S.insert({L(LINF,0), L(-LINF,0)}); C.insert(cp(L(LINF,0),L(-LINF,0))); } // for debug void print() { cout << "S : "; for (auto it : S) printf("(%lld,%lld)", it.a, it.b); puts(""); cout << "C : "; for (auto it : C) printf("(%lld,%lld)", it.n, it.d); puts(""); } void add(LL a, LL b) { const L p(a,b); It pos = S.insert(p).first; if (check(*it_m1(pos), p, *it_p1(pos))) { // 直線(a,b)が不要 S.erase(pos); return; } C.erase(cp(*it_m1(pos), *it_p1(pos))); { // 右方向の削除 It it = it_m1(pos); while(it!=S.begin() && check(*it_m1(it), *it, p)) --it; C_erase(it, it_m1(pos)); S.erase(++it,pos); pos = S.find(p); } { // 左方向の削除 It it = it_p1(pos); while(it_p1(it)!=S.end() && check(p,*it, *it_p1(it))) ++it; C_erase(++pos, it); S.erase(pos, it); pos = S.find(p); } C.insert(cp(*it_m1(pos), *pos)); C.insert(cp(*pos, *it_p1(pos))); } LL query(LL x) { const L &p = (--C.lower_bound(CP(x,1,L(0,0))))->p; return p.a*x + p.b; } private: It it_p1(It a){return ++a;} It it_m1(It a){return --a;} void C_erase(It a, It b) { for (It it=a; it!=b; ++it) C.erase(cp(*it, *it_p1(it))); } CP cp(const L &p1, const L &p2) { if (p1.a == LINF) return CP(-LINF,1,p2); if (p2.a == -LINF) return CP(LINF,1,p2); return CP(p1.b-p2.b, p2.a-p1.a, p2); } bool check(const L &p1, const L &p2, const L &p3) { if (p1.a==p2.a && p1.b <= p2.b) return 1; if (p1.a == LINF || p3.a == -LINF) return 0; return (p2.a-p1.a)*(p3.b-p2.b) >= (p2.b-p1.b)*(p3.a-p2.a); } }; LL N,A,B,W; LL ans = 0LL; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> N >> A >> B >> W; VL d(N+1); FOR(i,0,N){ cin >> d[i]; } CHT2 Q; VL dp(N+2,0); dp[0] = W; // dp(i) := 食べてi日目を終える FOR(i,0,N){ // i日目に食べる Q.add(-B*i,dp[i] + B*(i*i-i)/2+ A*i); dp[i+1] = B*(i*i+i)/2 + d[i] - A*i + (Q.query(i)); debug(dp[i]); } ans = LINF; FOR(i,0,N+1){ // i日目から食べてないのでストレスまみれ ans = min(ans, dp[i] - A*(N-i) +B*(N-i)*(N-i+1)/2); } cout << ans << "\n"; return 0; }