結果

問題 No.3527 Minimum Abs Sum
コンテスト
ユーザー detteiuu
提出日時 2026-05-04 22:20:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,733 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 186 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 177,636 KB
最終ジャッジ日時 2026-05-04 22:21:37
合計ジャッジ時間 36,309 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 4 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd
from functools import cmp_to_key

class Fraction:
    def __init__(self, top, bottom):
        GCD = gcd(top, bottom)
        if bottom < 0:
            top = -top
            bottom = -bottom
        self.top = top//GCD
        self.bottom = bottom//GCD

def to_fraction(n):
    if type(n) == int:
        return Fraction(n, 1)
    else:
        return n

def compare(L, R):
    L, R = L[0], R[0]
    L, R = to_fraction(L), to_fraction(R)
    a = L.top*R.bottom
    b = L.bottom*R.top
    if a < b:
        return -1
    elif a == b:
        return 0
    else:
        return 1
    
def max_f(L, R):
    return L if compare(L, R) == 1 else R

def min_f(L, R):
    return L if compare(L, R) == -1 else R

def ADD(L, R):
    L, R = to_fraction(L), to_fraction(R)
    l, r = L.bottom, R.bottom
    lt = L.top*r
    rt = R.top*l
    top = lt+rt
    bottom = l*r
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def SUB(L, R):
    L, R = to_fraction(L), to_fraction(R)
    l, r = L.bottom, R.bottom
    lt = L.top*r
    rt = R.top*l
    top = lt-rt
    bottom = l*r
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def MUL(L, R):
    L, R = to_fraction(L), to_fraction(R)
    top = L.top*R.top
    bottom = L.bottom*R.bottom
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def DIV(L, R):
    L, R = to_fraction(L), to_fraction(R)
    top = L.top*R.bottom
    bottom = L.bottom*R.top
    GCD = gcd(top, bottom)
    top //= GCD
    bottom //= GCD
    if bottom < 0:
        top = -top
        bottom = -bottom
    return Fraction(top, bottom)

def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AB = []
for i in range(N):
    if A[i] != 0:
        AB.append((A[i], B[i]))
A, B = list(map(list, zip(*AB)))
N = len(A)

C = []
SUM = 0
for i in range(N):
    if A[i] == 0: continue
    if A[i] < 0:
        A[i] = -A[i]
        B[i] = -B[i]
    C.append((Fraction(B[i], A[i]), A[i]))
    if 1 <= i: SUM += A[i]
cmp = cmp_to_key(compare)
C.sort(key=cmp)

l, r = C[0][1], SUM
SUM = 0
pre = C[0][0]
X = 0
ans = C[0][0]
for a, b in C[1:]:
    diff = SUB(a, pre)
    SUM = SUB(SUM, MUL(diff, r))
    SUM = ADD(SUM, MUL(diff, l))
    if compare((SUM, 0), (X, 0)) == -1:
        SUM = X
        ans = a
    r = SUB(r, b)
    l = ADD(l, b)
    pre = a

print(inverse(ans.top, ans.bottom))
0