結果

問題 No.3509 Get More Money
コンテスト
ユーザー tassei903
提出日時 2026-04-18 16:44:04
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 4,957 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 622 ms
コンパイル使用メモリ 85,376 KB
実行使用メモリ 157,528 KB
最終ジャッジ日時 2026-04-18 16:45:57
合計ジャッジ時間 111,777 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 57 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

"""

maxmize sum_{i <= n} -A[i]x[i] + C[i]y[i]

C[i]D[i] - minimize A[i]x[i] + B[i]y[i]

0 <= sum_{i <= n} x[i] - y[i] <= K (all n)
0 <= sum_{i <= n} x[i] - (D[i] - y[i]) <= K
sum(D) <= sum(x) + sum(y) <= sum(D) + K

d[1] <=  z[1] <= d[1] + K
d[1] + d[2] <= z[1] + z[2] <= d[1] + d[2] + K


x[i] = d[i] + K とする

x[i] > 0 となる i の中で max(p[i]) を選ぶ

"""
from heapq import *
# https://maspypy.com/segment-tree-のお勉強2
# verified : https://judge.yosupo.jp/problem/range_affine_range_sum
class LazySegmentTree:
    def __init__(self, N: int, op, e, mapping, composition, id_) -> None:
        self._N = N
        self._log = (N - 1).bit_length()
        self._size = 1 << self._log
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_
        self._data = [e] * (2 * self._size)
        self._lazy = [id_] * self._size

    def build(self, seq: list) -> None:
        """O(N)で初期化する, 個別にsetするとO(NlogN)になるので注意"""
        for i, x in enumerate(seq, self._size):
            self._data[i] = x
        for i in range(self._size - 1, 0, -1):
            self._data[i] = self._op(self._data[2 * i], self._data[2 * i + 1])
    
    def _push(self, i: int) -> None:
        if self._lazy[i] == self._id:
            return 
        self._data[2 * i] = self._mapping(self._lazy[i], self._data[2 * i])
        self._data[2 * i + 1] = self._mapping(self._lazy[i], self._data[2 * i + 1])
        if 2 * i < self._size:
            self._lazy[2 * i] = self._composition(self._lazy[i], self._lazy[2 * i])
            self._lazy[2 * i + 1] = self._composition(self._lazy[i], self._lazy[2 * i + 1])
        self._lazy[i] = self._id
        return

    def prod(self, L: int, R: int):
        """O(logN)で[L, R)の区間積を取得"""
        assert 0 <= L <= R <= self._N
        if L == R:
            return self._e
        L += self._size
        R += self._size
        for h in range(self._log, 0, -1):
            self._push(L >> h)
            self._push((R - 1) >> h)
        vL = self._e
        vR = self._e
        while L < R:
            if L & 1:
                vL = self._op(vL, self._data[L])
                L += 1
            if R & 1:
                vR = self._op(self._data[R - 1], vR)
            L //= 2
            R //= 2
        return self._op(vL, vR) 
    
    def apply(self, L: int, R: int, x) -> None:
        """O(logN)で[L, R)の更新"""
        assert 0 <= L <= R <= self._N
        if L == R:
            return
        L += self._size
        R += self._size
        L0, R0 = L, R
        for h in range(self._log, 0, -1):
            self._push(L >> h)
            self._push((R - 1) >> h)
        while L < R:
            if L & 1:
                self._data[L] = self._mapping(x, self._data[L])
                if L < self._size:
                    self._lazy[L] = self._composition(x, self._lazy[L])
                L += 1
            if R & 1:
                R -= 1
                self._data[R] = self._mapping(x, self._data[R])
                if R < self._size:
                    self._lazy[R] = self._composition(x, self._lazy[R])
            L //= 2
            R //= 2
        l0 = (L0 & -L0).bit_length()
        r0 = (R0 & -R0).bit_length()
        for i in range(1, self._log + 1):
            L0 //= 2
            R0 //= 2
            if i >= l0:
                self._data[L0] = self._op(self._data[2 * L0], self._data[2 * L0 + 1])
            if i >= r0:
                self._data[R0] = self._op(self._data[2 * R0], self._data[2 * R0 + 1])

def op(x, y):
    return min(x, y)

def mapp(f, x):
    return x + f

def comp(x, y):
    return x + y


inf = 10 ** 18
for _ in range(ni()):
    n, k = na()
    a = na()
    b = na()
    c = na()
    d = na()
            
    lst = LazySegmentTree(n, op, inf, mapp, comp, 0)
    xx = k
    f = []
    for i in range(n):
        xx += d[i]
        f.append(xx)
    lst.build(f)
        

    ans = sum(c[i] * d[i] for i in range(n))
    hq = [] 
    res = [0] * n
    for i in range(n):
        heappush(hq, (a[i], b[i], i))
        heappush(hq, (c[i], d[i], i))
        x = d[i]
        # print(hq, d[i], [lst.prod(i, i + 1) for i in range(n)])
        while x:
            p, q, j = heappop(hq)
            rest = min(q, lst.prod(j, n))
            y = min(x, rest)
            res[j] += y
            ans -= y * p
            x -= y
            lst.apply(j, n, -y)
            if y < rest:
                heappush(hq, (p, rest - y, j))
    print(ans)
    # print(res)
0