結果
問題 | No.31 悪のミックスジュース |
ユーザー |
![]() |
提出日時 | 2015-07-24 13:37:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 49 ms / 5,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 1,381 ms |
コンパイル使用メモリ | 165,316 KB |
実行使用メモリ | 7,500 KB |
最終ジャッジ日時 | 2024-09-14 15:52:15 |
合計ジャッジ時間 | 2,582 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)n;i++) #define all(c) (c).begin(),(c).end() #define mp make_pair #define pb push_back #define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) #define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pi; const int inf = (int)1e9; const double INF = 1e12, EPS = 1e-9; const int MX = 500000; int n, v; ll dp[MX + 10000], c[110]; int main(){ cin >> n >> v; rep(i, n) cin >> c[i + 1], c[i + 1] += c[i]; vector<pair<ll, ll>> p; rep(i, n) p.pb(mp(i + 1ll, c[i + 1])); sort(all(p), [](pair<ll, ll> a, pair<ll, ll> b){ return a.second * b.first < b.second * a.first; }); if(v <= n){ cout << c[n] << endl; return 0; } v -= n; rep(i, MX + 10000) dp[i] = 1e18; dp[0] = 0; rep(i, MX){ for(int j = 1; j <= n; j++) dp[i + j] = min(dp[i + j], dp[i] + c[j]); } if(v <= MX) cout << dp[v] + c[n] << endl; else{ //assert(0); ll a = p[0].first, b = p[0].second; int x = MX - MX % a + v % a - a; assert((v - x) % a == 0); cout << dp[x] + (v - x) / a * b + c[n] << endl; } //rep(i, n + 1) cerr<<c[i]<<(i==n?"\n":" "); return 0; }