레이팅 미적용전국 우유의 날을 맞아, 농부 존(Farmer John)은 우유 양동이를 특별한 가격에 팔고 있다! 존에게는 \(1\)부터 \(N\)까지 번호가 붙은 \(N\)개 (\(1 \leq N \leq 10^5\))의 상품이 있다. \(i\)번째 상품은 우유 \(2^{i-1}\)양동이를 \(a_i\) (\(1 \leq a_i \leq 10^9, a_i < a_{i+1}\)) 무니에 파는 것이다. 같은 상품을 음이 아닌 정수 번만큼 몇 번이든 구매할 수 있다.
당신은 \(Q\)개 (\(1 \leq Q \leq 10^4\))의 독립적인 질의를 생각하고 있다. 각 질의에서 당신은 정수 \(x\) (\(1 \leq x \leq 10^9\))를 떠올리고, 우유를 \(x\)양동이 이상 구매하는 데 드는 최소 비용이 얼마인지 궁금해한다.
문제 제공: Chongtian Ma
배점
- 입력 3-4: \(N \leq 2\)
- 입력 5-8: \(N \leq 10\)
- 입력 9-16: 추가 제약이 없다.
문제 제공: Chongtian Ma
첫째 줄에 두 정수 \(N\)과 \(Q\)가 주어진다.
다음 줄에 \(a_1, a_2, \ldots, a_N\)이 주어진다.
다음 \(Q\)개의 줄에는 각각 질의를 나타내는 정수 \(x\)가 주어진다.
각 질의에 대해, 최소 비용을 한 줄에 하나씩 출력한다.
이 문제에서 다루는 정수는 크기가 커서 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
2 4
10 15
1
2
6
710
15
45
55In the example above, Farmer John is offering 2 deals: 1 bucket of milk for 10
moonies and 2 buckets of milk for 15 moonies.
The cheapest cost to buy 1 bucket is just the cost of the 1 bucket deal and the
cheapest cost to buy 2 buckets is just the cost of the 2 bucket deal.
To get 6 buckets, the cheapest way is to purchase 3 of the 2 bucket deal for a
total of 45 moonies.
To get 7 buckets, the cheapest way is to purchase 3 of the 2 bucket deal and 1
of the 1 bucket deal for a total of 55 moonies.
4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
10110
20
30
30
40
50
60
60
120
760In this example, Farmer John is offering a total of 4 deals for 1, 2, 4, and 8
buckets. For each of the 10 queries, the corresponding output indicates the
minimum cost to purchase at least that amount of milk. Sometimes, it is cheaper
to purchase more than the specified amount.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Bronze