公式
B - 合格ラインの日々 / Days of the Passing Line 解説
by
B - 合格ラインの日々 / Days of the Passing Line 解説
by
sounansya
印刷ページ
\(\displaystyle B_k=\sum_{i=1}^k A_i\) と定義すると、条件は \(kA_k \geq B_k\) と表されます。
この \(B\) は 累積和 と呼ばれるもので、順に和を取ることで \(O(N)\) 時間で計算することができます。
したがって、\(B\) を高速に計算し、各 \(k\) に対して \(kA_k \geq B_k\) が成り立つか判定することでこの問題を解くことができます。
n = int(input())
a = list(map(int, input().split()))
b = a.copy()
for i in range(1, n):
b[i] += b[i - 1]
ans = 0
for k in range(n):
ans += (k + 1) * a[k] >= b[k]
print(ans)
投稿日時:
最終更新:
