tourist vs rainboy

tourist가 $i$번 문제를 해결하는 데 사용한 시간 $A_i$는 $i,i+1,\cdots,N$번 문제의 해결 시각에 포함된다. 따라서 tourist의 페널티는

$$\sum_{i=1}^{N}(N-i+1)A_i$$

이다.

rainboy의 경우 $A_i$는 $1,2,\cdots,i$번 문제의 해결 시각에 포함되므로 페널티는

$$\sum_{i=1}^{N}iA_i$$

이다.

따라서 구해야 하는 차이는

$$\sum_{i=1}^{N}(2i-N-1)A_i$$

이다. 입력을 한 번 순회하며 이 값을 계산하면 된다. 시간 복잡도는 $O(N)$이다.

Solution written by GPT5.6