結果

問題 No.165 四角で囲え！
ユーザー rpy3cpprpy3cpp
提出日時 2015-05-30 01:35:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 843 ms / 5,000 ms
コード長 2,105 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 87,364 KB
実行使用メモリ 80,092 KB
最終ジャッジ日時 2023-08-26 23:44:53
合計ジャッジ時間 9,521 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 404 ms
79,008 KB
testcase_01 AC 72 ms
71,220 KB
testcase_02 AC 71 ms
71,408 KB
testcase_03 AC 72 ms
71,148 KB
testcase_04 AC 71 ms
71,092 KB
testcase_05 AC 787 ms
79,256 KB
testcase_06 AC 183 ms
78,148 KB
testcase_07 AC 71 ms
71,176 KB
testcase_08 AC 72 ms
71,120 KB
testcase_09 AC 71 ms
71,168 KB
testcase_10 AC 72 ms
71,224 KB
testcase_11 AC 254 ms
78,528 KB
testcase_12 AC 170 ms
77,912 KB
testcase_13 AC 245 ms
77,752 KB
testcase_14 AC 164 ms
77,712 KB
testcase_15 AC 173 ms
77,736 KB
testcase_16 AC 668 ms
79,540 KB
testcase_17 AC 646 ms
79,928 KB
testcase_18 AC 843 ms
79,816 KB
testcase_19 AC 671 ms
80,092 KB
testcase_20 AC 644 ms
79,844 KB
testcase_21 AC 650 ms
79,864 KB
testcase_22 AC 648 ms
79,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def read_data():
    N, B = map(int, input().split())
    Xs = []
    Ys = []
    Ps = []
    for i in range(N):
        x, y, p = map(int, input().split())
        Xs.append(x)
        Ys.append(y)
        Ps.append(p)
    return N, B, Xs, Ys, Ps

def solve(N, B, Xs, Ys, Ps):
    if len(Xs) == 0:
        return 0
    Xs = compress(Xs)
    Ys = compress(Ys)
    if max(Xs) > max(Ys):
        Xs, Ys = Ys, Xs
    cum, cumP = preprocess(Xs, Ys, Ps)
    return find_max(cum, cumP, B)

def compress(As):
    Avals = list(set(As))
    Avals.sort()
    val2idx = {a:i for i, a in enumerate(Avals)}
    return [val2idx[a] for a in As]

def preprocess(Xs, Ys, Ps):
    max_x = max(Xs)
    max_y = max(Ys)
    mat = [[0] * (max_y + 2) for _ in range(max_x + 2)]
    for x, y, p in zip(Xs, Ys, Ps):
        mat[x + 1][y + 1] = p
    cum = [[0] * (max_y + 2) for _ in range(max_x + 2)]
    cumP = [[0] * (max_y + 2) for _ in range(max_x + 2)]
    for x in range(1, max_x + 2):
        cumx = cum[x]
        cumx_prev = cum[x - 1]
        cumPx = cumP[x]
        cumPx_prev = cumP[x - 1]
        matx = mat[x]
        tmp = 0
        tmpP = 0
        for y in range(1, max_y + 2):
            if matx[y]:
                tmp += 1
                tmpP += matx[y]
            cumx[y] = cumx_prev[y] + tmp
            cumPx[y] = cumPx_prev[y] + tmpP
    return cum, cumP

def find_max(cum, cumP, B):
    nrow = len(cum)
    ncol = len(cum[0])
    max_n = 0
    for t in range(nrow - 1):
        cum_t = cum[t]
        cumP_t = cumP[t]
        for b in range(t + 1, nrow):
            n = find_max_n(cum_t, cumP_t, cum[b], cumP[b], B, ncol)
            if n > max_n:
                max_n = n
    return max_n

def find_max_n(t, Pt, b, Pb, B, ncol):
    max_n = 0
    left = 0
    for right in range(1, ncol):
        p = Pb[right] - Pt[right]
        while p - Pb[left] + Pt[left] > B:
            left += 1
        n = b[right] - t[right] - b[left] + t[left]
        if n > max_n:
            max_n = n
    return max_n

if __name__ == '__main__':
    N, B, Xs, Ys, Ps = read_data()
    print(solve(N, B, Xs, Ys, Ps))
0