結果
問題 |
No.165 四角で囲え!
|
ユーザー |
![]() |
提出日時 | 2017-09-19 18:14:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,662 ms / 5,000 ms |
コード長 | 1,732 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 77,568 KB |
最終ジャッジ日時 | 2024-12-26 03:40:01 |
合計ジャッジ時間 | 14,461 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
def compression_mapping(xs): ys = [] for i in range(len(xs)): ys.append(i) ys.sort(key=xs.__getitem__) m = {} for i in ys: if xs[i] not in m: index = len(m) m[xs[i]] = index return m def compress(m, xs): ys = [] for i in range(len(xs)): ys.append(m[xs[i]]) return ys N,B = list(map(int, input().split(' '))) X = [0 for _ in range(N)] Y = [0 for _ in range(N)] P = [0 for _ in range(N)] for i in range(N): X[i],Y[i],P[i] = list(map(int, input().split(' '))) X = compress(compression_mapping(X), X) Y = compress(compression_mapping(Y), Y) index = [] for i in range(N): index.append(i) index.sort(key=X.__getitem__) solution = 0 for top in range(N+1): for bottom in range(top): count = 0 score = 0 right_end = 0 right_pointer = 0 left_end = 0 left_pointer = 0 while right_end < N: right_end += 1 while right_pointer < N and X[index[right_pointer]] < right_end: if bottom <= Y[index[right_pointer]] and Y[index[right_pointer]] < top: count += 1 score += P[index[right_pointer]] right_pointer += 1 while B < score: left_end += 1 while left_pointer < N and X[index[left_pointer]] < left_end: if bottom <= Y[index[left_pointer]] and Y[index[left_pointer]] < top: count -= 1 score -= P[index[left_pointer]] left_pointer += 1 solution = max(solution, count) print(solution)