結果

問題 No.3527 Minimum Abs Sum
コンテスト
ユーザー detteiuu
提出日時 2026-05-04 22:25:17
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,695 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 171 ms
コンパイル使用メモリ 85,568 KB
実行使用メモリ 167,612 KB
最終ジャッジ日時 2026-05-05 00:20:20
合計ジャッジ時間 27,303 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd

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

    def _to_fraction(self, x):
        return x if isinstance(x, Fraction) else Fraction(x, 1)

    def __eq__(self, other):
        other = self._to_fraction(other)
        return self.top == other.top and self.bottom == other.bottom
    
    def __ne__(self, other):
        other = self._to_fraction(other)
        return self.top != other.top or self.bottom != other.bottom
    
    def __lt__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom < self.bottom*other.top
    
    def __le__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom <= self.bottom*other.top
    
    def __gt__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom > self.bottom*other.top
    
    def __ge__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom >= self.bottom*other.top
        
    def __add__(self, other):
        other = self._to_fraction(other)
        GCD = gcd(self.bottom, other.bottom)
        bottom = self.bottom*other.bottom//GCD
        top1 = self.top*(bottom//self.bottom)
        top2 = other.top*(bottom//other.bottom)
        return Fraction(top1+top2, bottom)

    def __sub__(self, other):
        other = self._to_fraction(other)
        GCD = gcd(self.bottom, other.bottom)
        bottom = self.bottom*other.bottom//GCD
        top1 = self.top*(bottom//self.bottom)
        top2 = other.top*(bottom//other.bottom)
        return Fraction(top1-top2, bottom)

    def __mul__(self, other):
        other = self._to_fraction(other)
        return Fraction(self.top*other.top, self.bottom*other.bottom)
    
    def __truediv__(self, other):
        other = self._to_fraction(other)
        return Fraction(self.top*other.bottom, self.bottom*other.top)
    
    def __radd__(self, other):
        return self+other
    
    def __rsub__(self, other):
        return self._to_fraction(other)-self
    
    def __rmul__(self, other):
        return self*other
    
    def __rtruediv__(self, other):
        return self._to_fraction(other)/self
    
    def __int__(self):
        return self.top//self.bottom
    
    def __float__(self):
        return self.top/self.bottom
    
    def __str__(self):
        return f"{self.top}/{self.bottom}"
    
    def __hash__(self):
        return hash((self.top, self.bottom))
    
    def __bool__(self):
        return self.top != 0
    
    def __neg__(self):
        return Fraction(-self.top, self.bottom)
    
    def __abs__(self):
        return Fraction(abs(self.top), self.bottom)
    
    def get(self):
        return self.top, self.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:
        A[i] = -A[i]
        B[i] = -B[i]
    C.append((Fraction(B[i], A[i]), A[i]))
    SUM += A[i]
C.sort(key=lambda x:x[0])

l, r = C[0][1], SUM-C[0][1]
SUM = 0
pre = C[0][0]
X = 0
ans = C[0][0]
for a, b in C[1:]:
    diff = a-pre
    SUM -= diff*r
    SUM += diff*l
    if SUM < X:
        SUM = X
        ans = a
    r -= b
    l += b
    pre = a

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