結果

問題 No.3292 World Map Distance
コンテスト
ユーザー i_taku
提出日時 2025-10-17 09:41:14
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,046 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 246 ms
コンパイル使用メモリ 95,596 KB
実行使用メモリ 113,740 KB
最終ジャッジ日時 2026-07-15 18:55:18
合計ジャッジ時間 10,934 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)

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

print(ans)
0