BOJ#18234

LEVEL :

Gold4

문제 요약 :

토끼가 오리의 당근을 최대한 맛있게 먹는 방법은 무엇인가

해결 방안 :

pi 가 클 수로 나중에 먹는 것이 유리하다.
그래서 pi기준으로 정렬한 뒤,
t-n+1번째 부터 pi순서대로 먹으면 된다.

시간 복잡도 :

O(nlogn) Tim-sort

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n,t = map(int,input().strip().split())
    c = [list(map(int,input().split())) for i in range(n)]
    c.sort(key = lambda x:(x[1], x[0]))
    w= 0
    for i in range(n-1, -1, -1):
        w+= c[-(n-(i))][0] + c[-(n-(i))][1]*(t-n+i)
    print(w)