結果

問題 No.180 美しいWhitespace (2)
ユーザー 👑 rin204rin204
提出日時 2023-11-23 18:57:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,730 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 81,948 KB
実行使用メモリ 76,724 KB
最終ジャッジ日時 2024-09-26 08:17:40
合計ジャッジ時間 4,140 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,096 KB
testcase_01 AC 36 ms
52,224 KB
testcase_02 AC 35 ms
52,352 KB
testcase_03 AC 33 ms
52,224 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 125 ms
73,856 KB
testcase_10 AC 119 ms
74,368 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 121 ms
73,856 KB
testcase_20 AC 34 ms
51,840 KB
testcase_21 AC 33 ms
52,352 KB
testcase_22 AC 35 ms
52,096 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 37 ms
52,736 KB
testcase_26 AC 36 ms
52,352 KB
testcase_27 AC 37 ms
52,352 KB
testcase_28 AC 34 ms
52,224 KB
testcase_29 AC 34 ms
52,096 KB
testcase_30 AC 139 ms
76,288 KB
testcase_31 AC 142 ms
76,404 KB
testcase_32 AC 79 ms
69,120 KB
testcase_33 AC 123 ms
76,288 KB
testcase_34 AC 127 ms
76,316 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
A = [0] * n
B = [0] * n
for i in range(n):
    B[i], A[i] = map(int, input().split())

mi = [None] * n
ma = [None] * n
for i in range(n):
    l = 1
    r = 1 << 60
    for j in range(n):
        if i == j:
            continue
        if A[i] == A[j]:
            if B[i] > B[j]:
                r = -1
                break
        elif A[i] > A[j]:
            r = min(r, (B[j] - B[i]) // (A[i] - A[j]))
        else:
            db = B[i] - B[j]
            da = A[j] - A[i]
            l = max(l, (db + da - 1) // da)

    if l <= r:
        mi[i] = (l, r)

    l = 1
    r = 1 << 60
    for j in range(n):
        if i == j:
            continue
        if A[i] == A[j]:
            if B[i] < B[j]:
                r = -1
                break
        elif A[i] > A[j]:
            da = A[i] - A[j]
            db = B[j] - B[i]
            l = max(l, (db + da - 1) // da)
        else:
            r = min(r, (B[i] - B[j]) // (A[j] - A[i]))

    if l <= r:
        ma[i] = (l, r)


ans = 1 << 60
x = 1 << 60
for i in range(n):
    if mi[i] is None:
        continue

    l1, r1 = mi[i]
    for j in range(n):
        if i == j or ma[j] is None:
            continue

        l2, r2 = ma[j]

        if l2 <= l1 <= r1:
            ma_ = A[j] * l1 + B[j]
            mi_ = A[i] * l1 + B[i]
            if ma_ - mi_ < ans:
                ans = ma_ - mi_
                x = l1
            elif ma_ - mi_ == ans and l1 < x:
                x = l1
        if l1 <= l2 <= r1:
            ma_ = A[j] * l2 + B[j]
            mi_ = A[i] * l2 + B[i]
            if ma_ - mi_ < ans:
                ans = ma_ - mi_
                x = l2
            elif ma_ - mi_ == ans and l1 < x:
                x = l2


print(x)
0