結果

問題 No.165 四角で囲え！
ユーザー gew1fw
提出日時 2025-06-12 21:41:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,348 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,204 KB
実行使用メモリ 77,168 KB
最終ジャッジ日時 2025-06-12 21:46:34
合計ジャッジ時間 49,452 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    B = int(input[idx])
    idx += 1
    points = []
    for _ in range(N):
        x = int(input[idx])
        idx += 1
        y = int(input[idx])
        idx += 1
        p = int(input[idx])
        idx += 1
        points.append((x, y, p))
    
    # Sort points by Y-coordinate
    S = sorted(points, key=lambda p: p[1])
    
    max_count = 0
    
    # Iterate over all possible Y ranges (i,j)
    for i in range(len(S)):
        for j in range(i + 1, len(S)):
            subset = S[i + 1:j]
            if not subset:
                continue
            
            # Sort subset by X-coordinate
            sorted_subset = sorted(subset, key=lambda p: p[0])
            prefix = [0]
            for p in sorted_subset:
                prefix.append(prefix[-1] + p[2])
            
            # Sliding window to find max count
            left = 0
            current_sum = 0
            max_in_subset = 0
            for right in range(len(sorted_subset)):
                current_sum += sorted_subset[right][2]
                while current_sum > B and left <= right:
                    current_sum -= sorted_subset[left][2]
                    left += 1
                current_count = right - left + 1
                if current_count > max_in_subset:
                    max_in_subset = current_count
            if max_in_subset > max_count:
                max_count = max_in_subset
    
    # Consider the case where all points are included
    subset = S
    if subset:
        sorted_subset = sorted(subset, key=lambda p: p[0])
        prefix = [0]
        for p in sorted_subset:
            prefix.append(prefix[-1] + p[2])
        
        left = 0
        current_sum = 0
        max_in_subset = 0
        for right in range(len(sorted_subset)):
            current_sum += sorted_subset[right][2]
            while current_sum > B and left <= right:
                current_sum -= sorted_subset[left][2]
                left += 1
            current_count = right - left + 1
            if current_count > max_in_subset:
                max_in_subset = current_count
        if max_in_subset > max_count:
            max_count = max_in_subset
    
    print(max_count)

if __name__ == '__main__':
    main()
0