結果
| 問題 | No.974 最後の日までに |
| ユーザー |
 shibh308
|
| 提出日時 | 2019-12-07 13:30:01 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,885 bytes |
| コンパイル時間 | 265 ms |
| コンパイル使用メモリ | 11,212 KB |
| 実行使用メモリ | 166,836 KB |
| 最終ジャッジ日時 | 2023-09-07 22:30:25 |
| 合計ジャッジ時間 | 7,028 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
ソースコード
import bisect
n = 0
a = []
b = []
c = []
m = []
v = [[], []]
s = [[], []]
def dfs(i, flag, money, val):
if i == m:
if flag:
s[0].append((money, val))
v[0].append((money, val))
return
if not flag:
dfs(i + 1, True, money, val)
dfs(i + 1, False, money + a[i], val)
else:
dfs(i + 1, False, money - c[i], val + b[i])
def dfs2(i, flag, last_flag, money, val):
if i == n:
if last_flag:
s[1].append((money, val))
v[1].append((money, val))
return
if not flag:
dfs2(i + 1, True, last_flag, money, val)
if i == m:
dfs2(i + 1, False, True, money - c[i], val + b[i])
else:
dfs2(i + 1, False, last_flag, money + a[i], val)
else:
dfs2(i + 1, False, last_flag, money - c[i], val + b[i])
def calc(key1, key2, val1, val2):
ans = 0
for k, v in zip(key1, val1):
idx = bisect.bisect_left(key2, -k)
ans = max(ans, v + val2[idx])
return ans
def main():
global n, m, a, b, c
n = int(input())
for i in range(n):
a_, b_, c_ = tuple(map(int, input().split()))
a.append(a_)
b.append(b_)
c.append(c_)
m = n // 2
dfs(0, False, 0, 0)
dfs2(m, False, False, 0, 0)
v_keys = [[], []]
v_vals = [[], []]
s_keys = [[], []]
s_vals = [[], []]
for i in range(2):
v_tmp = []
s_tmp = []
for money, _ in v[i]:
v_tmp.append(money)
for money, _ in s[i]:
s_tmp.append(money)
v_tmp = sorted(v_tmp)
s_tmp = sorted(s_tmp)
for elm in v_tmp:
if not v_keys[i] or v_keys[i][-1] != elm:
v_keys[i].append(elm)
for elm in s_tmp:
if not s_keys[i] or s_keys[i][-1] != elm:
s_keys[i].append(elm)
v_vals[i] = [-int(1e18) for _ in range(len(v_keys[i]))]
s_vals[i] = [-int(1e18) for _ in range(len(s_keys[i]))]
for money, val in v[i]:
idx = bisect.bisect_left(v_keys[i], money)
assert(v_keys[i][idx] == money)
v_vals[i][idx] = val
for money, val in s[i]:
idx = bisect.bisect_left(s_keys[i], money)
assert(s_keys[i][idx] == money)
s_vals[i][idx] = val
for j in range(len(v_vals[i]) - 1, 0, -1):
v_vals[i][j - 1] = max(v_vals[i][j - 1], v_vals[i][j]);
for j in range(len(s_vals[i]) - 1, 0, -1):
s_vals[i][j - 1] = max(s_vals[i][j - 1], s_vals[i][j]);
s_keys[i].append(int(1e18))
s_vals[i].append(int(-1e18))
v_keys[i].append(int(1e18))
v_vals[i].append(int(-1e18))
ans = max(calc(s_keys[0], s_keys[1], s_vals[0], s_vals[1]), calc(v_keys[0], v_keys[1], v_vals[0], v_vals[1]))
print(ans)
if __name__ == '__main__':
main()