結果

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

ソースコード

diff #
raw source code 

from functools import cmp_to_key
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]))
def cmp(a, b):
    if (a[0]<0 and a[1]<0) or (a[0]>=0 and a[1]>=0):
        asign = 1
    else:
        asign = -1
    if (b[0]<0 and b[1]<0) or (b[0]>=0 and b[1]>=0):
        bsign = 1
    else:
        bsign = -1
    if asign<bsign:
        return -1
    elif asign>bsign:
        return 1
    if asign==1:
        if a[0]*b[1]<a[1]*b[0]:
            return -1
        elif a[0]*b[1]>a[1]*b[0]:
            return 1
        else:
            return 0
    else:
        if a[0]*b[1]<a[1]*b[0]:
            return 1
        elif a[0]*b[1]>a[1]*b[0]:
            return -1
        else:
            return 0
   
P.sort(key=cmp_to_key(cmp))
M.sort(key=cmp_to_key(cmp))

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