結果

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

ソースコード

diff #
raw source code 

from fractions import Fraction
import sys
input = sys.stdin.readline
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = []
P = []
Z = []
for i in range(N):
    if A[i]>0:
        P.append((A[i], B[i]))
    elif A[i]<0:
        M.append((A[i], B[i]))
    else:
        Z.append((A[i], B[i]))
P.sort(key=lambda x:Fraction(x[1], x[0]))
M.sort(key=lambda x:Fraction(x[1], x[0]))
PA = [0]
PB = [0]
for a, b in P:
    PA.append(PA[-1]+a)
    PB.append(PB[-1]+b)
MA = [0]
MB = [0]
for a, b in M:
    MA.append(MA[-1]+a)
    MB.append(MB[-1]+b)
SZ = 0
for a, b in Z:
    SZ += abs(b)
INF = 10**18
ans = INF
ans2 = INF
i = 0
j = 0
while i<len(P) or j<len(M):
    if i<len(P) and j<len(M):
        pa, pb = P[i]
        ma, mb = M[j]
        xp = Fraction(pb, pa)
        xm = Fraction(mb, ma)
        if xp<=xm:
            tmp = SZ
            tmp += (PB[-1]-PB[i]) - (PA[-1]-PA[i]) * xp
            tmp += (PA[i] * xp) - PB[i]
            tmp += MB[j] - MA[j] * xp
            tmp += (MA[-1]-MA[j]) * xp - (MB[-1]-MB[j])
            if ans > tmp:
                ans = tmp
                ans2 = xp
            elif ans==tmp and ans2 > xp:
                ans2 = xp
            i+=1
        else:
            tmp = SZ
            tmp += (PB[-1]-PB[i]) - (PA[-1]-PA[i]) * xm
            tmp += (PA[i] * xm) - PB[i]
            tmp += MB[j] - MA[j] * xm
            tmp += (MA[-1]-MA[j]) * xm - (MB[-1]-MB[j])
            if ans > tmp:
                ans = tmp
                ans2 = xm
            elif ans==tmp and ans2 > xm:
                ans2 = xm
            j+=1
    elif i<len(P):
        pa, pb = P[i]
        xp = Fraction(pb, pa)
        tmp = SZ
        tmp += (PB[-1]-PB[i]) - (PA[-1]-PA[i]) * xp
        tmp += (PA[i] * xp) - PB[i]
        tmp += MB[j] - MA[j] * xp
        tmp += (MA[-1]-MA[j]) * xp - (MB[-1]-MB[j])
        if ans > tmp:
            ans = tmp
            ans2 = xp
        elif ans==tmp and ans2 > xp:
            ans2 = xp
        i+=1
    else:
        ma, mb = M[j]
        xm = Fraction(mb, ma)
        tmp = SZ
        tmp += (PB[-1]-PB[i]) - (PA[-1]-PA[i]) * xm
        tmp += (PA[i] * xm) - PB[i]
        tmp += MB[j] - MA[j] * xm
        tmp += (MA[-1]-MA[j]) * xm - (MB[-1]-MB[j])
        if ans > tmp:
            ans = tmp
            ans2 = xm
        elif ans==tmp and ans2 > xm:
            ans2 = xm
        j+=1

ans3 = ans2.numerator * pow(ans2.denominator, MOD-2, MOD) % MOD
print(ans3)
0