結果

問題 No.165 四角で囲え!
ユーザー qwewe
提出日時 2025-05-14 12:55:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,441 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,492 KB
実行使用メモリ 84,364 KB
最終ジャッジ日時 2025-05-14 12:56:23
合計ジャッジ時間 25,195 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 5 WA * 8 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff #

n, b = map(int, input().split())
points = []
for _ in range(n):
    x, y, p = map(int, input().split())
    points.append((x, y, p))

max_count = 0

# Check individual points
for x, y, p in points:
    if p <= b:
        max_count = max(max_count, 1)

# Generate all unique x coordinates
unique_x = sorted({p[0] for p in points})

# Iterate over all possible x ranges [a, b]
for i in range(len(unique_x)):
    a_x = unique_x[i]
    for j in range(i, len(unique_x)):
        b_x = unique_x[j]
        # Collect points in x range [a_x, b_x]
        S = []
        sum_p = 0
        min_y = float('inf')
        max_y = -float('inf')
        for p in points:
            x, y, p_val = p
            if a_x <= x <= b_x:
                S.append(p)
                sum_p += p_val
                if y < min_y:
                    min_y = y
                if y > max_y:
                    max_y = y
        if not S:
            continue
        if sum_p > b:
            continue
        # Check validity: no point outside S has x in [a_x, b_x] and y in [min_y, max_y]
        valid = True
        for p in points:
            x, y, _ = p
            if (a_x <= x <= b_x) and (min_y <= y <= max_y):
                if p not in S:
                    valid = False
                    break
        if valid:
            current_count = len(S)
            if current_count > max_count:
                max_count = current_count

print(max_count)
0