카페 주문 구간 견적

문제

한 카페의 백엔드 담당자는 단체 주문을 위한 견적 기능을 개발한다. 카페에는 미리 정해진 순서로 나열된 N개의 주문 항목이 있다. 각 항목에는 할인과 세금을 적용하기 전의 가격이 붙어 있다. 같은 메뉴가 여러 항목에 등장하더라도 각 항목은 별도로 계산한다. 고객은 목록에서 연속한 구간을 선택하여 그 구간에 들어 있는 모든 항목을 한 번씩 주문한다. 견적 요청 하나에는 시작 번호 L, 끝 번호 R, 할인율 D가 주어진다. 먼저 L번부터 R번까지의 가격을 모두 더해 기본 금액 B를 구한다. 그다음 할인 금액을 B×D를 100으로 나눈 값의 소수 부분을 버린 정수로 계산한다. 할인 적용 금액 P는 기본 금액 B에서 이 할인 금액을 뺀 값이다. 할인 금액은 각 항목에서 따로 계산하지 않고 선택한 구간 전체의 기본 금액에서 한 번만 계산한다. 카페는 할인 적용 금액 P에 대해 10퍼센트의 세금을 추가한다. 세금은 P를 10으로 나눈 값의 소수 부분을 버린 정수다. 최종 견적 금액은 P와 세금을 더한 값이다. 모든 금액의 단위는 원이며, 계산 과정에서 반올림은 사용하지 않는다. 할인율이 0이면 할인 금액은 0원이고, 할인율이 100이면 할인 적용 금액과 세금은 모두 0원이다. 견적 요청은 Q개이며 각 요청은 서로 독립적이다. 어떤 요청을 처리해도 주문 항목의 가격이나 다른 요청의 할인율은 바뀌지 않는다. 서로 겹치는 구간이 여러 번 요청될 수도 있고, 같은 구간에 서로 다른 할인율이 주어질 수도 있다. 입력된 요청 순서대로 최종 견적 금액을 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1≤N,Q≤15,000이다. 둘째 줄에 각 주문 항목의 가격을 나타내는 정수 A_1, A_2, …, A_N이 주어진다. 모든 i에 대해 1≤A_i≤1,000이다. 다음 Q개 줄에는 정수 L, R, D가 주어진다. 1≤L≤R≤N이고 0≤D≤100이다.

출력

각 견적 요청에 대한 최종 견적 금액을 입력 순서대로 한 줄에 하나씩 정수로 출력한다.

4 3
105 210 35 80
1 2 10
2 4 0
1 4 100

312
357
0

1 3
19
1 1 5
1 1 50
1 1 100

20
11
0

출처: Devin.KR 자체 제작