結果

問題 No.3646 Decrement.
コンテスト
ユーザー kidodesu
提出日時 2026-09-18 17:16:24
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 398 ms / 2,000 ms
+ 101µs
コード長 1,040 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 72 ms
コンパイル使用メモリ 80,896 KB
実行使用メモリ 122,112 KB
最終ジャッジ日時 2026-09-18 17:16:53
合計ジャッジ時間 5,300 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 1
小課題1 5 % AC * 5
小課題2 5 % AC * 3
小課題3 20 % AC * 10
小課題4 30 % AC * 19
小課題5 10 % AC * 34
小課題6 30 % AC * 45
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
if sum(A) <= k:
    print(0)
    exit()
ans = A[0]+A[-1]
for i in range(n-1):
    ans += abs(A[i]-A[i+1])
n += 2
A = [-1] + A + [-1]
L = [i for i in range(n)]
R = [i+1 for i in range(n)]
from heapq import *
hq = []
i = 1
while i < n-1:
    j = i
    while j < n and A[i] == A[j]:
        j += 1
    if A[i-1] < A[i] and A[i] > A[j]:
        heappush(hq, (j-i, i, j))
    L[i] = L[j-1] = i
    R[i] = R[j-1] = j
    i = j

while hq and k:
    t, l, r = heappop(hq)
    if k < t: break
    if L[l] != l or R[l] != r:
        continue
    a = A[l]
    a0, a1 = A[l-1], A[r]
    na = max(a-k//t, a0, a1)
    #print(ans, a0, a, a1, na)
    ans -= 2*(a-na)
    k -= (a-na)*t
    nl, nr = l, r
    if a0 == na:
        nl = L[l-1]
    if a1 == na:
        nr = R[r]
    #print(ans, t, l, r, nl, nr, a, na)
    L[nl] = L[nr-1] = nl
    R[nl] = R[nr-1] = nr
    A[nl] = A[nr-1] = na
    if A[nl-1] < A[nl] and A[nl] > A[nr]:
        heappush(hq, (nr-nl, nl, nr))

print(ans)
0