結果
問題 |
No.409 ダイエット
|
ユーザー |
|
提出日時 | 2017-08-16 02:45:37 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 957 bytes |
コンパイル時間 | 86 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 24,832 KB |
最終ジャッジ日時 | 2024-10-13 11:12:49 |
合計ジャッジ時間 | 7,336 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 34 TLE * 1 -- * 36 |
ソースコード
from collections import deque N, A, B, W = map( int, input().split() ) D = list( map( int, input().split() ) ) dp = [ 0 for i in range( N + 1 ) ] def get_cost( x, rb ): d = rb - x - 1 return dp[ x ] + d * ( d + 1 ) // 2 * B - d * A + D[ rb - 1 ] dq = deque() dp[ 0 ] = W dq.append( [ 0, 1, N ] ) for i in range( 1, N + 1 ): while dq[ 0 ][ 2 ] < i: dq.popleft() dp[ i ] = get_cost( dq[ 0 ][ 0 ], i ) while len( dq ): x, lb, rb = dq[ len( dq ) - 1 ] if get_cost( x, lb ) >= get_cost( i, lb ): dq.pop() if len( dq ): dq[ len( dq ) - 1 ][ 2 ] = N else: break x, lb, rb = dq[ len( dq ) - 1 ][ 0 ], i + 1, N while rb - lb > 1: mid = lb + rb >> 1 if get_cost( x, mid ) >= get_cost( i, mid ): rb = mid else: lb = mid dq[ len( dq ) - 1 ][ 2 ] = rb - 1 dq.append( [ i, rb, N ] ) print( min( dp[ i ] + ( N - i ) * ( N - i + 1 ) // 2 * B - ( N - i ) * A for i in range( N + 1 ) ) )