N, K = map(int, input().split())
limit = 5001
# accum[i][j]: 身長i以下、体重j以下の生徒が何人いるか？
accum = [[0] * limit for _ in range(limit)]
for _ in range(N):
A, B = map(int, input().split())
accum[A][B] += 1
for i in range(1, limit):
for j in range(limit):
accum[i][j] += accum[i - 1][j]
for i in range(limit):
for j in range(1, limit):
accum[i][j] += accum[i][j - 1]
def count(i, j):
i2 = min(limit - 1, i + K + 1)
j2 = min(limit - 1, j + K + 1)
return accum[i][j] + accum[i2][j2] - accum[i][j2] - accum[i2][j]
ans = 0
for i in range(limit):
for j in range(limit):
ans = max(ans, count(i, j))
print(ans)
https://atcoder.jp/contests/typical90/tasks/typical90_cc
問題概要
N人の生徒の身長と体重が分かっている。身長が最も高い生徒と低い生徒の差、最も重い生徒と軽い生徒の差がともにK以下となるようにグループを作るとき、グループは最大何人にできるか？
ざっくり考え方
横軸身長、縦軸体重の二次元表に生徒をプロットする。 ↓ 入力例1
の図。
長さK(=4)の正方形に入るのは最大2人なので、答えは2になる。 なので、長さNの正方形をどこに置くとその中に入っている生徒数が最大になるかという問題になる。
解法
身長x以下、体重y以下の生徒が何人いるかを二次元累積和で求める。 始点(0, 0)から長さKの正方形を1マスずつ動かしていき、生徒数を求めていけばいい。
計算量は5000 ** 2。
https://atcoder.jp/contests/typical90/submissions/51994097