Coding 공부

import heapq
import sys

def dijkstra(S,E,TERM):
    INF = float('inf')
    distance_list = [INF]*(N+1)
    distance_list[S] = TERM
    node_list = []
    heapq.heappush(node_list,(TERM,S))

    while node_list:
        cur_time,cur_node = heapq.heappop(node_list)

        for next_node in graph[cur_node]:
            if time_spend_list.get((cur_node,next_node)) and time_spend_list[(cur_node,next_node)][0]<=cur_time<=time_spend_list[(cur_node,next_node)][1]:
                spend_time = time_spend_list[(cur_node,next_node)][1] + graph[cur_node][next_node]
            else:
                spend_time = cur_time + graph[cur_node][next_node]
            
            if distance_list[next_node] > spend_time:
                distance_list[next_node] = spend_time
                heapq.heappush(node_list,(spend_time,next_node))

    return distance_list


input = sys.stdin.readline

N,M = map(int,input().split())

start_point,end_point,king_term,G = map(int,input().split())

king_visit_list = list(map(int,input().split()))


graph = [{} for _ in range(N+1)]

for _ in range(M):
    x,y,times = map(int,input().split())

    graph[x][y] = min(graph[x].get(y,float('inf')),times)
    graph[y][x] = min(graph[y].get(x,float('inf')),times)



time_spend_list = {}

king_time = 0
for ind in range(G-1):
    start,ends = king_visit_list[ind],king_visit_list[ind+1]
    time_spend_list[(start,ends)] = (king_time,king_time+graph[start][ends])
    time_spend_list[(ends,start)] = (king_time,king_time+graph[start][ends])
    king_time += graph[start][ends]


result = dijkstra(start_point,end_point,king_term)


print(result[end_point]-king_term)

import sys

sys.setrecursionlimit(100001)


def dfs(node):
    visited[node] = True
    child_node = []
    for next_node in graph[node]:
        if not visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][0] = 1
        return
    else:
        for child in child_node:
            dfs(child)

        for child in child_node:
            if dp[child][0]:
                dp[node][1] = 1
                break
        else:
            dp[node][0] = 1

N = int(input())
graph = [[] for _ in range(N+1)]


for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
visited = [False]*(N+1)
dp = [[0]*2 for _ in range(N+1)]
dfs(1)

answer = min(list(map(sum,list(zip(*dp)))))
print(answer)

string = input()
duck = 'quack'
cnt = 0
result = []
answer = 0
for st in string:
    flag = True
    for ind in range(len(result)):
        if duck[(duck.index(result[ind][-1])+1)%5] == st:
            result[ind].append(st)
            flag = False
            break

    if flag:
        if st != 'q':
            answer = -1
            break
        result.append([st])

if answer == -1:
    print(answer)
else:
    for i in result:
        if len(i)%5 != 0:
            print(-1)
            break
    else:
        print(len(result))

    

S = input()

duck = {'q':0,'u':1,'a':2,'c':3,'k':4}

queue = []
answer = 0
for sound in S:
    flag = True
    for ind in range(len(queue)):
        if (queue[ind] + 1)%5 == duck[sound]:
            queue[ind] = (queue[ind] + 1)%5
            flag = False
            break
    if flag:
        if duck[sound] != 0:
            answer = -1
            break
        queue.append(0)


if answer == -1:
    print(-1)
else:
    for num in queue:
        if num != 4:
            print(-1)
            break
    else:
        print(len(queue))

N = int(input())
arr = list(map(int,input().split()))

LIS = [arr[0]]
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]

LIS_CNT = len(LIS)
print(LIS_CNT)

import sys
input = sys.stdin.readline
while True:
    N,M = map(int,input().split())
    if not N+M:
        break

    arr = [list(map(int,input().split())) for _ in range(N)]
    maze = [[0 for _ in range(M)] for _ in range(N)]
    for y in range(M):
        maze[0][y] = arr[0][y]
    for x in range(1,N):
        for y in range(M):
            if arr[x][y]:
                maze[x][y] = maze[x-1][y] + arr[x][y]

    result = 0

    for x in range(N):
        col_idx = 0
        stack = []
        while col_idx<M:
            if stack:
                if stack[-1] <= maze[x][col_idx]:
                    stack.append(maze[x][col_idx])
                    col_idx += 1
                else:
                    size_stack = len(stack)
                    min_value = stack[-1]
                    cu_idx = -1
                    for i in range(size_stack):
                        result = max(result,min_value*(i+1))
                        cu_idx -= 1
                        if abs(cu_idx)<=size_stack and min_value > stack[cu_idx]:
                            min_value = stack[cu_idx]
                    

                    if maze[x][col_idx]:
                        stack.append(maze[x][col_idx])
                    else:
                        stack.clear()
                    col_idx += 1

            else:
                if maze[x][col_idx]:
                    stack.append(maze[x][col_idx])
                col_idx += 1
        if stack:
            size_stack = len(stack)
            min_value = stack[-1]
            cu_idx = -1
            for i in range(size_stack):
                result = max(result,min_value*(i+1))
                cu_idx -= 1
                if abs(cu_idx)<=size_stack and min_value > stack[cu_idx]:
                    min_value = stack[cu_idx]

    print(result)

        

import sys
input = sys.stdin.readline

while True:
    N,M = map(int,input().split())

    arr = [[0] + list(map(int,input().split())) + [0] for i in range(N)]
    if N+M == 0:
        break
    for i in range(1,N):
        for j in range(1,M+1):
            if arr[i][j]:
                arr[i][j] = arr[i-1][j] + 1
    result = 0
    for i in range(N):
        stack = [0]
        for j in range(1,M+2):
            while stack and  arr[i][j] < arr[i][stack[-1]]:
                height = arr[i][stack[-1]]
                stack.pop()
                width = j-stack[-1] - 1
                result = max(result,height*width)
            stack.append(j)
    print(result)

N = int(input())

arr = list(map(int,input().split()))
dp = [*arr]
for i in range(len(arr)-1):
    for j in range(i+1,len(arr)):
        if arr[i]< arr[j]:
            dp[j] = max(dp[j],dp[i] + arr[j])

print(max(dp))

T = int(input())

for _ in range(T):
    day = int(input())

    arr = list(map(int,input().split()))
    answer = 0
    ind = day-1
    max_value = -1
    max_list = []
    while ind >=0:
        if arr[ind] > max_value:
            answer = answer - sum(max_list) + len(max_list)*max_value
            max_list = []
            max_value = arr[ind]
        else:
            max_list.append(arr[ind])

        ind -= 1
    if max_list:
        answer = answer - sum(max_list) + len(max_list)*max_value
    print(answer)

import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N = int(input())
    arr = list(map(int,input().split()))
    max_value = arr[-1]
    answer = 0
    for ind in range(N-2,-1,-1):
        if arr[ind] > max_value:
            max_value = arr[ind]
        else:
            answer = answer + max_value - arr[ind]
    print(answer)

import sys

input = sys.stdin.readline

N = int(input())

arr = list(map(int,input().split()))

dp = [[ True  if i == j else False for j in range (N)]  for i in range(N)]
for i in range(N-1):
    if arr[i] == arr[i+1]:
        dp[i][i+1] = True

for i in range(2,N):
    for j in range(N-i):
        if arr[j] == arr[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = True

M = int(input())

for _ in range(M):
    x,y = map(int,input().split())
    if dp[x-1][y-1]:
        sys.stdout.write('1\n')
    else:
        sys.stdout.write('0\n')