結果
問題 | No.31 悪のミックスジュース |
ユーザー | zimpha |
提出日時 | 2017-12-12 22:27:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 121 ms / 5,000 ms |
コード長 | 608 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 86,964 KB |
実行使用メモリ | 76,740 KB |
最終ジャッジ日時 | 2023-10-12 17:19:52 |
合計ジャッジ時間 | 2,957 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,280 KB |
testcase_01 | AC | 101 ms
76,088 KB |
testcase_02 | AC | 102 ms
76,512 KB |
testcase_03 | AC | 103 ms
76,340 KB |
testcase_04 | AC | 104 ms
76,404 KB |
testcase_05 | AC | 105 ms
76,740 KB |
testcase_06 | AC | 77 ms
71,160 KB |
testcase_07 | AC | 104 ms
76,044 KB |
testcase_08 | AC | 121 ms
76,680 KB |
testcase_09 | AC | 110 ms
76,232 KB |
testcase_10 | AC | 77 ms
71,116 KB |
testcase_11 | AC | 89 ms
76,568 KB |
testcase_12 | AC | 97 ms
76,536 KB |
testcase_13 | AC | 82 ms
76,240 KB |
testcase_14 | AC | 104 ms
76,672 KB |
testcase_15 | AC | 93 ms
76,604 KB |
testcase_16 | AC | 91 ms
76,364 KB |
ソースコード
def solve(): n, v = list(map(int, input().split())) c = list(map(int, input().split())) s = [x for x in c] for i in range(1, n): s[i] += s[i - 1] v -= n if v <= 0: return s[-1] m = min(20000, v) dp = [0] * (m + 1) x = 0 for i in range(n): if s[i] * (x + 1) < s[x] * (i + 1): x = i for i in range(0, m + 1): dp[i] = 2 ** 60 if (v - i) % (x + 1) == 0: dp[i] = (v - i) // (x + 1) * s[x] for i in range(m, -1, -1): for j in range(n): if i + j + 1 > m: continue dp[i] = min(dp[i], dp[i + j + 1] + s[j]) return dp[0] + s[-1] print(solve())