ゆるふわ競技プログラミングオンサイト at FORCIA #9
コンテスト日時
2026/11/07 (Sa) 14:15 - 16:45

A - Clear The Context

Milk
2
s
1024
MB
150
点

問題文

yurufuwa AI は、会話履歴を保存しながら依頼に答える AI です。文章の長さは「トークン」という単位で表され、利用量もこの単位で数えます。

siro53 君は yurufuwa AI に $N$ 個の依頼を順番に送ります。最初、会話履歴の長さは $0$ トークンです。

各整数 $i$($1 \leq i \leq N$)について、$i$ 番目の依頼を送ると、次の処理が順に行われます。

  1. 会話履歴の長さが $A_i$ トークン増える。
  2. 会話履歴の長さと同じ数のトークンを消費する。

また、siro53 君は、次の操作を高々 $1$ 回行うことができます。

整数 $i$($1 \leq i \leq N$)を $1$ つ選ぶ。$i$ 番目の依頼の処理がすべて終了した直後に、会話履歴の長さを $0$ トークンにする。

この操作ではトークンを消費せず、それまでに消費したトークン数も減りません。操作後の依頼は、長さが $0$ トークンになった会話履歴を引き継いで処理します。

$N$ 個すべての依頼を送るまでに消費するトークン数の合計の最小値を求めてください。

制約

  • $2 \leq N \leq 200$
  • $1 \leq A_i \leq 10^5$($1 \leq i \leq N$)
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A_1 \space A_2 \space \ldots \space A_N$

出力

$N$ 個すべての依頼を送るまでに消費するトークン数の合計の最小値を 1 行に出力してください。

入力例 1
5 3 1 4 1 5
出力例 1
22

$3$ 番目の依頼と $4$ 番目の依頼の間で会話履歴を $0$ にすると、各依頼で消費するトークン数は $3,4,8,1,6$ となり、合計は $22$ です。これが最小値となります。

入力例 2
4 100 1 1 1
出力例 2
106

$1$ 番目の依頼と $2$ 番目の依頼の間で会話履歴を $0$ にすると、各依頼で消費するトークン数は $100,1,2,3$ となり、合計は $106$ です。これが最小値となります。

提出
C++23 (g++ 12.2.0)