結果

問題 No.1122 Plane Tickets
ユーザー maspymaspy
提出日時 2020-07-22 23:44:38
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 547 ms / 1,000 ms
コード長 1,138 bytes
コンパイル時間 106 ms
コンパイル使用メモリ 11,140 KB
実行使用メモリ 30,248 KB
最終ジャッジ日時 2023-09-05 22:17:10
合計ジャッジ時間 23,454 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 547 ms
30,104 KB
testcase_01 AC 330 ms
30,016 KB
testcase_02 AC 383 ms
30,236 KB
testcase_03 AC 455 ms
30,020 KB
testcase_04 AC 342 ms
30,244 KB
testcase_05 AC 347 ms
30,112 KB
testcase_06 AC 339 ms
30,108 KB
testcase_07 AC 358 ms
30,024 KB
testcase_08 AC 382 ms
30,236 KB
testcase_09 AC 335 ms
30,240 KB
testcase_10 AC 311 ms
30,000 KB
testcase_11 AC 327 ms
30,116 KB
testcase_12 AC 333 ms
30,004 KB
testcase_13 AC 372 ms
30,132 KB
testcase_14 AC 364 ms
30,248 KB
testcase_15 AC 334 ms
29,948 KB
testcase_16 AC 361 ms
30,136 KB
testcase_17 AC 324 ms
30,068 KB
testcase_18 AC 357 ms
30,176 KB
testcase_19 AC 317 ms
30,200 KB
testcase_20 AC 357 ms
30,120 KB
testcase_21 AC 334 ms
30,080 KB
testcase_22 AC 335 ms
30,232 KB
testcase_23 AC 334 ms
29,944 KB
testcase_24 AC 392 ms
30,088 KB
testcase_25 AC 360 ms
30,040 KB
testcase_26 AC 347 ms
30,108 KB
testcase_27 AC 364 ms
30,116 KB
testcase_28 AC 387 ms
29,948 KB
testcase_29 AC 329 ms
30,032 KB
testcase_30 AC 323 ms
29,960 KB
testcase_31 AC 381 ms
30,108 KB
testcase_32 AC 543 ms
30,008 KB
testcase_33 AC 536 ms
30,068 KB
testcase_34 AC 317 ms
30,040 KB
testcase_35 AC 320 ms
30,008 KB
testcase_36 AC 308 ms
30,216 KB
testcase_37 AC 308 ms
30,180 KB
testcase_38 AC 307 ms
30,048 KB
testcase_39 AC 327 ms
29,956 KB
testcase_40 AC 322 ms
30,108 KB
testcase_41 AC 307 ms
30,068 KB
testcase_42 AC 327 ms
30,056 KB
testcase_43 AC 317 ms
30,016 KB
testcase_44 AC 347 ms
30,128 KB
testcase_45 AC 304 ms
30,132 KB
testcase_46 AC 359 ms
30,052 KB
testcase_47 AC 330 ms
30,076 KB
testcase_48 AC 353 ms
29,896 KB
testcase_49 AC 532 ms
29,948 KB
testcase_50 AC 524 ms
30,068 KB
testcase_51 AC 381 ms
29,960 KB
testcase_52 AC 389 ms
30,076 KB
testcase_53 AC 385 ms
30,048 KB
testcase_54 AC 395 ms
30,248 KB
testcase_55 AC 390 ms
30,020 KB
testcase_56 AC 379 ms
30,044 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import numpy as np
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, d, e = map(int, read().split())

A = np.array([
    [1,0,0,0,0],
    [0,1,0,0,0],
    [0,0,1,0,0],
    [0,0,0,1,0],
    [0,0,0,0,1],
    [1,1,0,0,1],
    [1,1,1,0,0],
    [0,1,1,1,0],
    [0,0,1,1,1],
    [1,0,0,1,1],
], np.int64)
v = np.array([0,0,0,0,0,a,b,c,d,e])

cand = []
for s in itertools.combinations(range(10), 5):
    A1 = np.concatenate([A[i] for i in s]).reshape(5,5)
    v1 = np.array([v[i] for i in s])
    D = np.linalg.det(A1)
    if D == 0.0:
        continue
    x = np.linalg.solve(A1, v1)
    if np.any(x < -2):
        continue
    cand.append(x.astype(np.int64))

ans = 0
nums = (a,b,c,d,e)
for x in cand:
    for eps in itertools.product(range(-1,2), repeat=5):
        y = x + np.array(eps)
        if np.any(y < 0):
            continue
        ok = True
        for i in range(5):
            if y[i] + y[(i-1)%5] + y[(i+1)%5] > nums[i]:
                ok = False
                break
        if ok:
            ans = max(ans, y.sum())
print(ans)
0