結果
問題 | No.1174 盆栽の剪定 |
ユーザー |
![]() |
提出日時 | 2020-08-18 00:19:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 216 ms / 2,000 ms |
コード長 | 581 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 119,936 KB |
最終ジャッジ日時 | 2024-10-11 11:31:42 |
合計ジャッジ時間 | 4,988 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
n = int(input()) assert 1 <= n <= 10**5 a = [0, *map(int, input().split())] for i in a: assert 0 <= i <= 10**9 dp = [[0] * (n + 1) for i in range(37)] for i in range(n, 0, -1): lg = i.bit_length() - 1 for j in range(-lg, lg + 1, 2): cnt1 = 0 cnt2 = 0 if i * 2 <= n: cnt1 += max(0, dp[j + 1][i * 2]) cnt2 += max(0, dp[j - 1][i * 2]) if i * 2 + 1 <= n: cnt1 += max(0, dp[j - 1][i * 2 + 1]) cnt2 += max(0, dp[j + 1][i * 2 + 1]) dp[j][i] = a[i] * j + max(cnt1, cnt2) print(dp[0][1])