結果
| 問題 |
No.3292 World Map Distance
|
| コンテスト | |
| ユーザー |
detteiuu
|
| 提出日時 | 2025-10-03 22:39:02 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,950 ms / 3,000 ms |
| コード長 | 1,160 bytes |
| コンパイル時間 | 405 ms |
| コンパイル使用メモリ | 82,440 KB |
| 実行使用メモリ | 284,024 KB |
| 最終ジャッジ日時 | 2025-10-03 22:39:32 |
| 合計ジャッジ時間 | 27,809 ms |
|
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
from bisect import bisect_left
N, X, Y = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]
INF = 1<<60
def compress(A):
S = sorted(set(A))
D = dict()
for i in range(len(S)):
D[S[i]] = i
return D, S
def func(A, limit):
B = []
for a in A:
B.append(a)
B.append((a+limit//2)%limit)
B.append((a+limit//2+1)%limit)
B.sort()
D, S = compress(B)
L = len(D)
cum = [0]*(L*2+1)
cumC = [0]*(L*2+1)
SUM = 0
for a in A:
cum[D[a]+1] += a
cum[D[a]+1+L] += a+limit
cumC[D[a]+1] += 1
cumC[D[a]+1+L] += 1
SUM += a
for i in range(1, L*2+1):
cum[i] += cum[i-1]
cumC[i] += cumC[i-1]
S *= 2
for i in range(L, L*2):
S[i] += limit
ans = -INF
for i in range(L):
mid = bisect_left(S, S[i]+limit//2+limit%2)
right = bisect_left(S, S[i]+limit)
ans = max(ans, ((cum[mid]-cum[i])-S[i]*(cumC[mid]-cumC[i]))+((S[i]+limit)*(cumC[right]-cumC[mid])-(cum[right]-cum[mid])))
return ans
B = [x-1 for x, y in xy]
C = [y-1 for x, y in xy]
print(func(B, X)+func(C, Y))
detteiuu