結果

問題 No.3292 World Map Distance
ユーザー pitP
提出日時 2025-10-04 16:18:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,132 ms / 3,000 ms
コード長 1,446 bytes
コンパイル時間 436 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 265,788 KB
最終ジャッジ日時 2025-10-04 16:19:01
合計ジャッジ時間 18,236 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import defaultdict

N, X, Y = map(int, input().split())
x, y = [-1] * N, [-1] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
    x[i] -= 1
    y[i] -= 1

def f(N, z, L):
    slopes = defaultdict(int)
    zs = set()
    a = 0
    wa = 0

    for i in range(N):
        if L & 1 :
            top1 = (z[i] + L // 2) % L
            top2 = (z[i] + L // 2 + 1) % L

            zs.add(z[i])
            zs.add(top1)
            zs.add(top2)

            slopes[z[i]] += 2
            slopes[top1] -= 1
            slopes[top2] -= 1

            if z[i] < L // 2:
                a -= 1
                wa += z[i]
            elif z[i] == L // 2:
                wa += L // 2
            else:
                a += 1
                wa += L - z[i]
        else:
            top = (z[i] + L // 2) % L

            zs.add(z[i])
            zs.add(top)

            slopes[z[i]] += 2
            slopes[top] -= 2

            if z[i] < L // 2:
                a -= 1
                wa += z[i]
            else:
                a += 1
                wa += L - z[i]
        # print("i, wa", i, wa)

    zs = list(zs)
    zs.sort()

    prv = 0
    ans = wa

    for pos in zs:
        add = slopes[pos]
        # print(pos, add, ans, wa)
        wa += (pos - prv) * a
        ans = max(ans, wa)

        prv = pos
        a += add

    return ans

print(f(N, x, X) + f(N, y, Y))
# print(f(N, x, X))
# print(f(N, y, Y))
0