/*
* Problem :: 13335 / 트럭
*
* Kind :: Simulation
*
* Insight
* - 주어지는 트럭들의 순서대로 다리를 건너야 한다
* + 주어지는 트럭들의 순서대로 건네줄 자료구조가 필요하다
* # Queue 를 사용하자
* 다리는 다리를 건너길 시작하는 트럭들을 넣어주고 다리를 다 건넌 트럭들을 빼주어야 한다
* + 뒤에서 트럭을 넣어주고 앞에서 트럭을 빼줄 자료구조가 필요하다
* # Deque 을 사용하자
*
* Point
* - 생각해 볼 점들
* + 다리를 건너길 시작한 트럭들을 다리위에 놓아줄 때,
* 초기 이동한 단위길이를 0 으로 할 것인가? 1 로 할 것인가?
* + 다리를 건너길 시작하는 트럭을 넣어주는 작업을 먼저할 것인가,
* 다리를 다 건넌 트럭을 빼주는 작업을 먼저할 것인가?
* + 다리 위 트럭들의 무게 총합을 언제 갱신시켜 줄 것인가?
* + 다리 위에 있는 트럭들의 움직임을 어떻게 추적할 것인가?
* + 모든 트럭이 다리를 건넌 것을 어떻게 확인할 것인가?
* + 시간은 언제 증가시켜줄 것인가?
* + 다리의 단위길이가 w 일때,
* 트럭이 w 단위길이만큼 움직였을 때 다리를 건넌 것으로 봐야할까?
* 아니면 w+1 단위길이만큼 움직였을 때 다리를 건넌 것으로 봐야할까?
* # 정답은 없다, 각자의 논리에 따른 구현에 있어서 위와 같은 점들이 조금씩 달라지기에
*
* - 저는...
* + 일단 다리위 트럭들의 무게 합을 쉽게 다루기 위해
* 다리를 다 건넌 트럭들을 먼저 빼줘서 다리의 무게를 줄여주고
* 그 다음 대기중인 트럭들을 넣어서 다리의 무게를 늘리는 방향으로 구현했다
* + 다리를 건너길 시작한 트럭들의 초기 이동한 단위길이는 0 으로 설정한 후,
* 트럭을 넣고 빼준뒤에, 다리 위 트럭들의 건넌 단위길이를 1 증가시켜주었다
* + Truck 이라는 구조체를 선언해서 트럭의 무게와 건넌 단위길이를 추적했다
* + 대기중인 트럭과 다리위 트럭이 없으면 트럭 모두가 다리를 건넌것으로 간주했다
* + 트럭 모두가 다리를 건너지 않았으면 시간을 1초 증가시켰다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
#define endl '\n'
// Set up : Global Variables
struct Truck { int w, d; }; /* w - 트럭의 무게, d - 트럭이 다리위에서 움직인 단위길이 */
// Set up : Functions Declaration
/* None */
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int N, W, L;
cin >> N >> W >> L;
queue<Truck> waiting; /* 대기중인 트럭들을 담은 Queue */
for (int i=0; i<N; i++) {
int w; cin >> w;
waiting.push({w, 0});
}
// Process
deque<Truck> bridge; /* 다리 위에 있는 트럭들을 담은 Deque */
int bw = 0; /* 현재 다리 위의 무게 */
int time = 0; /* 시간 카운터 */
/* 대기중인 트럭과 다리위의 트럭이 모두 비어있지 않으면
* 즉, 트럭들이 모두 다리를 건너지 않았으면 */
while (not(waiting.empty() && bridge.empty())) {
/* 시간 증가 */
time++;
/* 다 건넌 트럭 다리위에서 빼주기 */
if (not(bridge.empty())) {
Truck t = bridge.front(); /* 다리를 가장 많이 건넌 트럭 */
if (t.d == W) { /* 위의 트럭이 다리를 다 건넜다면 */
bridge.pop_front(); /* 다리에서 빼줌 */
bw -= t.w; /* 다리의 현재 무게 갱신 */
}
}
/* 건너길 시작한 트럭 다리위에 넣어주기 */
if (not(waiting.empty())) {
Truck t = waiting.front(); /* 대기중인 트럭 중 첫번째 트럭 */
if (bw + t.w <= L) { /* 현재 다리의 무게 + 위의 트럭의 무게 <= 최대하중 이면 */
bridge.push_back(t); /* 다리에 넣어줌 */
waiting.pop(); /* 대기열에서는 빼줌 */
bw += t.w; /* 다리의 현재 무게 갱신 */
}
}
/* 매 단위시간마다, 다리 위에 있는 모든 트럭들이 1 단위길이 만큼 이동 */
for (Truck &t : bridge) {
t.d++;
}
}
// Control : Output
cout << time << endl;
}
// Helper Functions
/* None */