23022번 - 숙제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (하단 참고) | 512 MB | 167 | 56 | 44 | 34.646% |
문제
Albert는 앞으로 n개의 숙제를 해야한다 (편의상 1번부터 n번까지 번호가 붙어있다).
현재 시각은 S 이고, i번째 숙제의 내용은 정해진 시각 t[i]에 공개 된다 (어떤 숙제는 이미 공개 되었지만 Albert가 아직 제출 하지 않았을 수 있다). 각 숙제별로 벌점이 있어서, 만약 Albert가 i번째 숙제를 제출한 시각이 y[i] 라면 (y[i] - t[i]) × v[i] 만큼의 벌점이 부여된다.
숙제는 어렵지 않아서 모든 숙제는 내용이 공개 되는 즉시 풀어서 제출할 수 있지만, 숙제를 하나 제출하고나면 반드시 최소한의 휴식을 취해야 한다. Albert가 취할 수 있는 최소한의 휴식은 "1 단위 시간" 이다 (필요하다면 더 많이 쉬는 것도 가능하다).
예를 들어 n = 5, S = 3, t = [1, 2, 3, 4, 5], 그리고 v = [8, 3, 2, 13, 3]이라 하자.
- 숙제를 순서대로 할 경우, 각 숙제를 제출한 시각은 y = [3, 4, 5, 6, 7]이 된다 (현재 시각이 3임에 유의하자). 이 경우, 총 벌점은 2 × 8 + 2 × 3 + 2 × 2 + 2 × 13 + 2 × 3 = 58 이다.
- 숙제를 1, 4, 2, 5, 3번 순서로 할 경우, 각 숙제를 제출한 시각은 y = [3, 5, 7, 4, 6]이 된다. 이 경우, 총 벌점은 2 × 8 + 3 × 3 + 4 × 2 + 0 × 13 + 1 × 3 = 36 이다.
- 숙제를 1, 5, 4, 3, 2 순서대로 할 경우, 각 숙제를 제출한 시각은 y = [3, 8, 7, 6, 5]이 된다. 이때, 숙제 1을 시각 3에 제출하고 숙제 5가 공개될 때 까지 "2 단위 시간" 만큼 휴식한다. 이 경우, 총 벌점은 2 × 8 + 6 × 3 + 4 × 2 + 2 × 13 + 0 × 3 = 42 이다.
이 예제에서 두 번째 방법이 벌점을 최소화 하는 방법이다.
Albert가 모든 숙제를 다 제출하면서 달성 가능한 최소한의 벌점이 몇점인지 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 세 줄에 걸쳐 주어진다.
첫 줄에 두 정수 n과 S가 공백으로 구분되어 주어진다.
둘째 줄에 숙제가 언제 나오는지 나타내는 n개의 정수가 (t[1], ..., t[n]) 공백으로 구분되어 주어진다.
셋째 줄에 숙제의 벌점을 나타내는 n개의 정수가 (v[1], ..., v[n]) 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답인 최소 벌점을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 100,000
- 1 ≤ S ≤ 2,000,000,000
- 1 ≤ t[i] ≤ 2,000,000,000
- 1 ≤ v[i] ≤ 40,000
예제 입력 1
2 5 3 1 2 3 4 5 8 3 2 13 3 5 30 10 20 30 40 50 8 3 2 13 3
예제 출력 1
36 197
예제 1: 본문에서 다루었다.
예제 2: 숙제를 1-2-3-4-5 순서대로 하는 것이 최선이다.
시간 제한
- Java 8: 5 초
- PyPy3: 8 초
- Java 8 (OpenJDK): 5 초
- Java 11: 5 초
- Kotlin (JVM): 5 초
- Java 15: 5 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호