結果

問題 No.3292 World Map Distance
コンテスト
ユーザー i_taku
提出日時 2025-10-17 09:42:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,071 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 109,336 KB
最終ジャッジ日時 2025-10-17 09:42:49
合計ジャッジ時間 12,752 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left


N, X, Y = map(int, input().split())
XX = []
YY = []
for _ in range(N):
    x, y = map(int, input().split())
    XX.append(x)
    YY.append(y)

XX.sort()
YY.sort()
XX = XX + [x + X for x in XX]
YY = YY + [y + Y for y in YY]
cum_x = [0] * (2 * N + 1)
cum_y = [0] * (2 * N + 1)
for i in range(2 * N):
    cum_x[i + 1] = cum_x[i] + XX[i]
    cum_y[i + 1] = cum_y[i] + YY[i]

def dist(cum, l, r):
    return cum[r] - cum[l]

def calc(cum, pos, ll, mid):
    lr = rl = bisect_left(pos, mid, ll, ll + N)
    rr = ll + N
    llen = lr - ll
    rlen = rr - rl
    d1 = mid * llen - dist(cum, ll, lr)
    d2 = dist(cum, rl, rr) - mid * rlen
    return d1 + d2

def cost(cum, pos, ll):
    left = pos[ll]
    right = pos[ll + N - 1]
    m1 = (left + right) // 2
    m2 = m1 + 1
    cost1 = calc(cum, pos, ll, m1)
    cost2 = calc(cum, pos, ll, m2)
    return min(cost1, cost2)

cost_x = 0
cost_y = 0
for ll in range(N):
    cost_x = max(cost_x, cost(cum_x, XX, ll))
    cost_y = max(cost_y, cost(cum_y, YY, ll))
    
ans = cost_x + cost_y
print(ans)
0