結果

問題 No.489 株に挑戦
ユーザー lam6er
提出日時 2025-04-16 01:08:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 254 ms / 1,000 ms
コード長 3,007 bytes
コンパイル時間 655 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 181,028 KB
最終ジャッジ日時 2025-04-16 01:10:08
合計ジャッジ時間 6,796 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import deque, defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    D = int(input[idx]); idx +=1
    K = int(input[idx]); idx +=1
    x = []
    for _ in range(N):
        x.append(int(input[idx]))
        idx +=1
    
    # Precompute sliding window maximum for window size D
    max_sliding = [0] * N
    dq = deque()
    for i in range(N):
        # Remove elements smaller than current from the end
        while dq and x[i] >= x[dq[-1]]:
            dq.pop()
        dq.append(i)
        # Remove elements out of the window [i-D+1, i]
        while dq and dq[0] < i - D + 1:
            dq.popleft()
        if i >= D-1:
            max_sliding[i] = x[dq[0]]
        else:
            max_sliding[i] = 0  # Not used for j where j+D <= N-1
    
    # Precompute sparse table for range maximum query
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1
    k_max = log_table[N] + 1 if N > 0 else 0
    st = []
    if N > 0:
        st.append(x.copy())
        for k in range(1, k_max):
            prev = st[k-1]
            current = []
            length = 1 << k
            for i in range(N - length + 1):
                current.append(max(prev[i], prev[i + (length // 2)]))
            st.append(current)
    
    def query_max(l, r):
        if l > r:
            return -1
        length = r - l + 1
        if length == 0:
            return -1
        k = log_table[length]
        max_val = max(st[k][l], st[k][r - (1 << k) + 1])
        return max_val
    
    # Precompute value_indices
    value_indices = defaultdict(list)
    for i in range(N):
        value_indices[x[i]].append(i)
    
    max_profit = 0
    best_j = -1
    best_k = -1
    
    for j in range(N-1):
        start = j + 1
        end = min(j + D, N-1)
        if start > end:
            continue
        # Compute max_val
        if j + D <= N-1:
            max_val = max_sliding[j + D]
        else:
            max_val = query_max(start, end)
        if max_val <= x[j]:
            continue
        # Find earliest k in [start, end] where x[k] == max_val
        indices = value_indices.get(max_val, [])
        if not indices:
            continue
        pos = bisect.bisect_left(indices, start)
        if pos < len(indices) and indices[pos] <= end:
            k = indices[pos]
        else:
            continue
        current_profit = K * (max_val - x[j])
        if current_profit > max_profit:
            max_profit = current_profit
            best_j = j
            best_k = k
        elif current_profit == max_profit:
            # Check if (j, k) is lex smaller than current best
            if (j < best_j) or (j == best_j and k < best_k):
                best_j = j
                best_k = k
    
    if max_profit > 0:
        print(max_profit)
        print(best_j, best_k)
    else:
        print(0)

if __name__ == "__main__":
    main()
0