結果
問題 |
No.3292 World Map Distance
|
ユーザー |
![]() |
提出日時 | 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))