結果

問題 No.165 四角で囲え！
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:01:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,120 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 78,456 KB
最終ジャッジ日時 2025-04-09 21:03:36
合計ジャッジ時間 47,064 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    B = int(data[idx+1])
    idx += 2
    points = []
    for _ in range(N):
        x = int(data[idx])
        y = int(data[idx+1])
        p = int(data[idx+2])
        points.append((x, y, p))
        idx += 3
    
    # Sort by X
    sorted_x = sorted(points, key=lambda point: point[0])
    x_coords = [point[0] for point in sorted_x]
    n = N
    
    max_points = 0
    
    for i in range(n + 1):
        # Determine left_val and right_val for X
        if i == 0:
            left_val = -float('inf')
        else:
            left_val = sorted_x[i-1][0]
        start_i = bisect.bisect_right(x_coords, left_val)
        
        for j in range(i + 1, n + 1):
            if j <= n:
                right_val = sorted_x[j-1][0] if (j-1 < n) else float('inf')
            else:
                right_val = float('inf')
            
            end_j = bisect.bisect_left(x_coords, right_val)
            
            # Extract points between start_i and end_j
            selected = sorted_x[start_i:end_j]
            if not selected:
                continue
            
            # Sort selected points by Y
            sorted_y = sorted(selected, key=lambda point: point[1])
            y_list = [point[1] for point in sorted_y]
            p_list = [point[2] for point in sorted_y]
            
            # Sliding window to find maximum points with sum <= B
            current_sum = 0
            left = 0
            current_max = 0
            for right in range(len(p_list)):
                current_sum += p_list[right]
                while current_sum > B:
                    current_sum -= p_list[left]
                    left += 1
                current_max = max(current_max, right - left + 1)
                if current_max == len(p_list):
                    break  # Can't get better than this
            
            if current_max > max_points:
                max_points = current_max
    
    print(max_points)

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