연습문제
[21년 재직자 대회 본선] 트럭
- 난이도
- Lv. 4
- 제출
- 107 명
- 참가자
- 16 명
- 정답률
- 32.14 %
- 지원 언어
-
CC++JavaPythonJavaScript
로그인 후 문제풀이가 가능합니다.
언어별 시간/메모리
언어 | 시간 | 메모리 |
---|---|---|
JavaScript | 4초 | 1024MB |
C | 2초 | 1024MB |
C++ | 2초 | 1024MB |
Java | 4초 | 1024MB |
Python | 4초 | 1024MB |
현대자동차그룹의 트럭 디자이너로 일하는 당신은 신차의 크기를 결정하려고 한다.
총 N명의 소비자에게 신차 구매의사를 조사했다.
i (1≤i≤N)번째 소비자는 Ai 개의 제안을 보냈는데, 이 중 j (1≤j≤Ai)번째 제안은 “신차의 크기가 Si,j 이상이라면 차량 한 대를 Pi,j원에 구매할 용의가 있다”는 것이다.
하지만 소비자 각각에 맞춘 차량을 생산하기에는 설비를 위한 비용이 막대해질 것이므로, 신차의 크기를 하나로 결정해야한다.
각 소비자는 트럭을 2대 이상 구매하지는 않을 것이다. 따라서, 당신은 각 소비자마다 그 소비자가 제시한 제안 중 하나를 수락하거나, 그 소비자의 제안을 모두 거절할 것이다. 이 때 당신이 정한 신차의 크기가 소비자의 여러가지 제안을 만족할 수 있다.
당신은 매출에 따라 신차의 크기를 얼마로 설정해야 하는지를 알아보고자, M가지의 시나리오를 고려해 보기로 하였다. 당신은 모든 k (1≤k≤M)에 대해, 총 Qk원의 매출을 내려면, 신차의 크기가 최소 얼마여야 하는지를 구해야 한다.
제약조건
주어지는 모든 수는 정수이다.
1≤N≤100,000
모든 i,j (1≤i≤N, 1≤j≤Ai)에 대해 1≤Si,j, Pi,j≤109
1≤M≤100,000
모든 k (1≤k≤M)에 대해, 1≤Qk≤109
입력형식
첫 번째 줄에 N이 주어진다.
다음 N개의 줄에는 소비자의 제안에 대한 정보가 주어진다
이 중 i (1≤i≤N)번째 줄의 형식은 다음과 같다: Ai Si,1 Pi,1 … Si,Ai Pi,Ai
그 다음 줄에 시나리오의 개수 M이 주어진다.
마지막 줄에 M개의 정수 Q1, Q2,…, QM이 공백 하나씩을 사이로 두고 주어진다.
출력형식
M개의 수를 한 칸의 공백을 두고 출력한다.
이 중 k (1≤k≤M)번째 수는
Qk원 이상의 매출을 낼 수 있다면, 이 때 신차의 최소 크기이다.
Qk원 이상의 매출을 낼 수 없다면, -1이다.
입력예제1
4 1 1 1 1 2 2 1 3 3 1 4 4 10 1 2 3 4 5 6 7 8 9 10
출력예제1
1 2 2 3 3 3 4 4 4 4
신차의 크기가 1이라면, 1번 소비자의 제안만 수락 할 수 있으므로, 총 1원의 매출을 얻을 수 있다.
신차의 크기가 2이라면, 1,2번 소비자의 제안을 수락 할 수 있으므로, 총 1+2=3원의 매출을 얻을 수 있다.
신차의 크기가 3이라면, 1,2,3번 소비자의 제안을 수락 할 수 있으므로, 총 1+2+3=6원의 매출을 얻을 수 있다.
신차의 크기가 4이라면, 모든 소비자의 제안을 수락 할 수 있으므로, 총 1+2+3+4=10원의 매출을 얻을 수 있다.
입력예제2
5 2 10 17 5 19 2 8 7 10 21 3 3 3 9 13 11 14 3 5 3 1 2 9 15 1 9 11 11 21 31 35 54 79 80 100 3 5 7 9
출력예제2
5 8 9 9 10 11 -1 3 3 5 5
일부 시나리오에 대해 설명한다.
신차의 크기가 8일 때, 아래와 같이 제안을 수락하면 총 32원의 매출을 얻을 수 있다.
1번 소비자의 2번 제안(크기 5 이상)을 수락하여, 19원을 얻을 수 있다.
2번 소비자의 1번 제안(크기 8 이상)을 수락하여, 7원을 얻을 수 있다.
3번 소비자의 1번 제안(크기 3 이상)을 수락하여, 3원을 얻을 수 있다.
4번 소비자의 1번 제안(크기 5 이상)과 2번 제안(크기 1 이상)을 모두 만족하므로 더 좋은 조건인 1번 제안을 수락하여, 3원을 얻을 수 있다.
신차의 크기가 10일 때, 아래와 같이 제안을 수락하면 총 79원의 매출을 얻을 수 있다.
1번 소비자의 1번 제안(크기 10 이상)과 2번 제안(크기 5 이상)을 모두 만족하므로 더 좋은 조건인 2번 제안을 수락하여, 19원을 얻을 수 있다.
2번 소비자의 1번 제안(크기 8 이상)과 2번 제안(크기 10 이상)을 모두 만족하므로 더 좋은 조건인 2번 제안을 수락하여, 21원을 얻을 수 있다.
3번 소비자의 1번 제안(크기 3 이상)과 2번 제안(크기 9 이상)을 모두 만족하므로 더 좋은 조건인 2번 제안을 수락하여, 13원을 얻을 수 있다.
4번 소비자의 1번 제안(크기 5 이상)과 2번 제안(크기 1 이상)과 3번 제안(크기 9 이상)을 모두 만족하므로 가장 좋은 조건인 3번 제안을 수락하여, 15원을 얻을 수 있다.
5번 소비자의 1번 제안(크기 9 이상)을 수락하여, 11원을 얻을 수 있다.