結果
問題 |
No.31 悪のミックスジュース
|
ユーザー |
![]() |
提出日時 | 2015-04-15 20:57:38 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 789 bytes |
コンパイル時間 | 1,388 ms |
コンパイル使用メモリ | 159,988 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 15:50:12 |
合計ジャッジ時間 | 1,928 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define MAX 25000 long long dp[MAX]; int main() { int N, V; cin >> N >> V; vector<long long> C(N); for (int i = 0; i < N; i++) { cin >> C[i]; } int best = 0; for (int i = 1; i < N; i++) { C[i] += C[i - 1]; if (C[i] * (best + 1) <= C[best] * (i + 1)){ best = i; } } long long ans = 0; ans += C[N - 1]; V -= N; if (V > 20000){ long long skip = (V - 20000) / (best + 1); V -= skip * (best + 1); ans += skip * C[best]; } for (int i = 0; i < MAX; i++) { dp[i] = (long long)2e18; } dp[0] = 0; for (int i = 0; i < V; i++) { for (int j = 0; j < N; j++) { if (i + j + 1 >= MAX) continue; dp[i + j + 1] = min(dp[i + j + 1], dp[i] + C[j]); } } ans += dp[V]; cout << ans << endl; cin >> ans; }