Ebihurai Search

2 secs 1024 MB

Kurolium

問題

提出

テストケース

解説

この問題は値段のリスト $C$ の累積和をまとめたリストを二分探索することで解くことができます。

数列のソートに $O(N log N)$ , 累積和を求めるのに $O(N)$ , クエリ処理に $O(Q log N)$
よって今回の制約に間に合わせることができます。

xxxxxxxxxx
 
from bisect import *
​
N, M, Q = map(int, input().split())
A = int(input())
C  = sorted([*map(int, input().split())])
​
sc = [0]
for i in range(N):
    sc.append(sc[-1] + C[i])
​
for _ in range(Q):
    X = int(input())
    
    n = bisect_right(sc, X + A) - 1
    if n >= M:
        print(n)
        
    else:
      print(bisect_right(sc, X) - 1)
​