結果
問題 | No.31 悪のミックスジュース |
ユーザー |
|
提出日時 | 2022-05-10 04:26:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 830 bytes |
コンパイル時間 | 1,876 ms |
コンパイル使用メモリ | 177,668 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-17 09:04:38 |
合計ジャッジ時間 | 2,642 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ ll n, v, sumv = 0; cin >> n >> v; vector<ll> a(n); vector<pair<ll,ll>> b(n); for(int i = 0; i < n; i++){ cin >> a[i]; sumv += a[i]; b[i]={sumv, i + 1}; } sort(b.begin(),b.end(),[&](pair<ll,ll> l, pair<ll,ll> r){ return l.first * r.second < r.first * l.second; }); ll ans = sumv, d; v -= min(v, n); d = max(0ll, (v - 10000) / b[0].second); v -= d * b[0].second; ans += d * b[0].first; vector<ll> dp(v + 1, 1ll << 62); dp[0] = 0; for(int i = 0; i < n; i++){ ll c, sv; tie(c, sv) = b[i]; for(int j = 0; j + sv <= v; j++){ dp[j + sv] = min(dp[j + sv], dp[j] + c); } } ans += dp[v]; cout << ans << endl; }