結果
問題 | No.165 四角で囲え! |
ユーザー | ckawatak |
提出日時 | 2017-09-19 18:04:41 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,698 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,364 KB |
実行使用メモリ | 76,732 KB |
最終ジャッジ日時 | 2024-04-25 18:13:01 |
合計ジャッジ時間 | 11,787 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 35 ms
52,744 KB |
testcase_02 | AC | 36 ms
52,756 KB |
testcase_03 | AC | 36 ms
53,808 KB |
testcase_04 | AC | 37 ms
53,808 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 38 ms
53,932 KB |
testcase_09 | AC | 38 ms
53,032 KB |
testcase_10 | AC | 36 ms
53,436 KB |
testcase_11 | WA | - |
testcase_12 | AC | 914 ms
76,260 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 993 ms
76,388 KB |
testcase_19 | WA | - |
testcase_20 | AC | 552 ms
76,240 KB |
testcase_21 | AC | 524 ms
69,424 KB |
testcase_22 | AC | 531 ms
69,244 KB |
ソースコード
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) 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)