結果
問題 | No.409 ダイエット |
ユーザー |
![]() |
提出日時 | 2016-09-12 07:45:57 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,057 bytes |
コンパイル時間 | 733 ms |
コンパイル使用メモリ | 65,964 KB |
実行使用メモリ | 6,912 KB |
最終ジャッジ日時 | 2024-06-26 09:59:50 |
合計ジャッジ時間 | 5,276 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 92 |
ソースコード
#include <iostream> #include <deque> #include <algorithm> #define rep(i, n) for(int i = 0; i < (n); ++i) using namespace std; typedef long long ll; typedef __int128 lll; const ll inf = 1e12; int n, a, b, w; int d[300000]; ll dp[300001]; deque<int> k; ll pt(int k){ return -ll(k) * b; } ll ct(int k){ return dp[k] + ll(k) * a + k * ll(k + 1) / 2 * b; } ll f(int k, int x){ return pt(k) * x + ct(k); } bool rm(int p, int q, int r){ return lll(ct(q) - ct(r)) * (pt(p) - pt(q)) >= lll(ct(p) - ct(q)) * (pt(q) - pt(r)); } void calc(){ dp[0] = w; for(int i = 1; i <= n; ++i){ while(k.size() >= 2 && rm(k[k.size() - 2], k.back(), i - 1)){ k.pop_back(); } k.push_back(i - 1); while(k.size() >= 2 && f(k[0], i) >= f(k[1], i)){ k.pop_front(); } dp[i] = f(k[0], i) + d[i - 1] + i * ll(i - 1) / 2 * b - ll(i - 1) * a; } } int main(){ cin >> n >> a >> b >> w; rep(i, n){ cin >> d[i]; } calc(); ll ans = inf; rep(i, n + 1){ ans = min(dp[n - i] + i * ll(i + 1) / 2 * b - ll(i) * a, ans); } cout << ans << endl; return 0; }