結果
問題 |
No.165 四角で囲え!
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()