레이팅 미적용베시는 배고픈 소이다. 매일 저녁 식사 때, 헛간에 건초 더미가 있으면 베시는 건초 더미를 하나 먹는다. 농부 존은 베시가 굶는 것을 원하지 않아서, 어떤 날에는 건초 더미 배달을 보내는데, 배달은 아침에(저녁 식사 전에) 도착한다. 구체적으로, \(d_i\)일에 농부 존은 \(b_i\)개의 건초 더미를 배달한다 (\(1\leq d_i \leq 10^{14}\), \(1 \leq b_i \leq 10^9\)).
처음 \(T\)일 동안 베시가 먹는 건초 더미의 총 개수를 구한다.
출제자: Brandon Wang
배점
- 입력 4-7: \(T \le 10^5\)
- 입력 8-13: 추가 제약이 없다.
출제자: Brandon Wang
첫째 줄에 \(N\)과 \(T\) (\(1 \le N \le 10^5\), \(1 \le T \le 10^{14}\))가 주어진다.
다음 \(N\)개의 줄에 각각 \(d_i\)와 \(b_i\)가 주어진다. 추가로 \(1\le d_1
처음 \(T\)일 동안 베시가 먹는 건초 더미의 개수를 출력한다.
이 문제에서 다루는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의한다.
1 5
1 22Two haybales arrive on the morning of day \(1\). Bessie eats one haybale for
dinner on day \(1\) and another haybale on day \(2\). On days \(3 \ldots 5\), there
are no more haybales for Bessie to eat. In total, Bessie eats \(2\) haybales
during the first \(5\) days.
2 5
1 2
5 103Two haybales arrive on the morning of day \(1\). Bessie eats one haybale on days
\(1\) and \(2\). There are no haybales for Bessie to eat on days \(3\) and \(4\). On the
morning of day \(5\), \(10\) haybales arrive. Bessie eats one haybale for dinner on
day \(5\). In total, Bessie eats \(3\) haybales during the first \(5\) days.
2 5
1 10
5 105\(10\) haybales arrive on the morning of day \(1\). Bessie eats one haybale on days
\(1 \ldots 4\). On the morning of day \(5\), another \(10\) haybales arrive, meaning
there are \(16\) haybales in the barn. For dinner on day \(5\), Bessie eats another
haybale. In total, Bessie eats \(5\) haybales during the first \(5\) days.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Bronze