結果
問題 | No.31 悪のミックスジュース |
ユーザー |
![]() |
提出日時 | 2016-02-17 16:48:21 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 2,032 bytes |
コンパイル時間 | 1,723 ms |
コンパイル使用メモリ | 162,808 KB |
実行使用メモリ | 11,392 KB |
最終ジャッジ日時 | 2024-09-14 15:52:55 |
合計ジャッジ時間 | 2,126 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; namespace { typedef double real; typedef long long ll; template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; os << "[" << vs[0]; for (int i = 1; i < vs.size(); i++) os << " " << vs[i]; return os << "]"; } int N; ll V; vector<ll> C; void input() { cin >> N >> V; C.resize(N); for (int i = 0; i < N; i++) cin >> C[i]; } void solve() { vector<ll> S(N, 0); // [0, k]を1[L]ずつまぜたジュースのk+1[L]の値段 S[0] = C[0]; for (int i = 1; i < N; i++) { S[i] = S[i - 1] + C[i]; } V -= N; int k = N - 1; for (int i = 0; i < N; i++) { real c = real(S[i]) / (i + 1); if (c < real(S[k]) / (k + 1)) { k = i; } } const ll INF = LLONG_MAX / 4LL; if (V <= 0) { cout << S[N - 1] << endl; return; } ll dp[N * N + 1][N + 1]; for (int j = 0; j <= N; j++) dp[0][j] = 0; for (int i = 1; i <= N * N; i++) for (int j = 0; j <= N; j++) dp[i][j] = INF; for (int i = 1; i <= N * N; i++) { for (int j = 1; j <= N; j++) { dp[i][j] = min(dp[i][j], dp[i][j - 1]); if (i - j >= 0) { dp[i][j] = min(dp[i][j], dp[i - j][j] + S[j - 1]); } else { dp[i][j] = min(dp[i][j], S[j - 1]); } } } //for (int i = 0; i <= N; i++) cout << i << " -> " << dp[i][N] << endl; ll ans = INF; ans = min(ans, S[k] * ((V + k) / (k + 1))); for (int i = 1; i <= N * N; i++) { ll v = V - i; ans = min(ans, dp[i][N] + max(0LL, S[k] * ((v + k) / (k + 1)))); } cout << ans + S[N - 1] << endl; } } int main() { input(); solve(); return 0; }