Coding 공부

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

arr = list(map(int,input().split()))
dp = [0]*(N+1)
result = 0


left = 0
right = 0
sum_temp = 0
while right <=N:
    if sum_temp >=K:
        while sum_temp >= K:
            dp[right] = max(dp[right],dp[left]+sum_temp-K)
            sum_temp -= arr[left]
            left += 1
    else:
        dp[right] = max(dp[right],dp[right-1])
        if right == N:
            break
        sum_temp += arr[right]
        right += 1
print(dp[N])

import sys

sys.setrecursionlimit(100001)
def find_min_right_over_k(left):
    global K
    low = left -1
    high = N
    while low + 1 < high:
        mid = (low+high)//2
        if prefix_sum[mid] - prefix_sum[left-1] >=K:
            high = mid
        else:
            low = mid
    return high




def solution(left):
    if left > N:
        return 0
    if dp[left] != -1:
        return dp[left]
    pass_hear_value = solution(left+1)
    right = find_min_right_over_k(left)
    eat_left_right = prefix_sum[right]-prefix_sum[left-1]-K+solution(right+1)
    max_value = max(pass_hear_value,eat_left_right)
    dp[left] = max_value
    return dp[left]

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

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

dp = [-1]*(N+1)

prefix_sum = [0]+arr[:]
for k in range(1,N+1):
    prefix_sum[k] += prefix_sum[k-1]


print(solution(1))

N = int(input())

INF = float('inf')



arr = [list(map(int,input().split())) for _ in range(N)]
result = float('inf')
for first_room in range(3):
    dp = [[INF]*3 for _ in range(N)]
    dp[0][first_room] = arr[0][first_room]
    for i in range(1,N-1):
        for k in range(3):
            for j in range(3):
                if k !=j:
                    dp[i][k] = min(dp[i-1][j]+arr[i][k],dp[i][k])

    for i in range(3):
        for j in range(3):
            if i != j and i != first_room:
                dp[N-1][i] = min(dp[N-2][j]+arr[N-1][i],dp[N-1][i])
    result = min(result,min(dp[N-1]))

print(result)

N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]


INF = float('inf')
result = INF
for first_room_color in range(3):
    dp = [[0]*3 for _ in range(N)]
    for i in range(3):
        if i == first_room_color:
            dp[0][i] = arr[0][i]
        else:
            dp[0][i] = INF

    for ind in range(1,N):
        dp[ind][0] = arr[ind][0] + min(dp[ind-1][1],dp[ind-1][2])
        dp[ind][1] = arr[ind][1] + min(dp[ind-1][0],dp[ind-1][2])
        dp[ind][2] = arr[ind][2] + min(dp[ind-1][0],dp[ind-1][1])

    for last_room_color in range(3):
        if last_room_color != first_room_color:
            if result > dp[N-1][last_room_color]:
                result = dp[N-1][last_room_color]

print(result)

def find_prime_number():
    global N
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False

    for num in range(2,N+1):
        if numbers[num]:
            for num_multi in range(num*2,N+1,num):
                numbers[num_multi] = False
    prime_number = []
    for num in range(N+1):
        if numbers[num]:
            prime_number.append(num)
    return prime_number



N = int(input())


prime_numbers = find_prime_number()
DP = [0]*40001



DP[0] = 1
for prime_number in prime_numbers:
    for num in range(prime_number,N+1):
        DP[num] = (DP[num]+DP[num-prime_number])%123456789


print(DP[N])

import sys
input = sys.stdin.readline

T = int(input())

INF = 10**9
for _ in range(T):
    N = int(input())
    books = list(map(int,input().split()))
    prefix_sum = [0]*(N+1)
    dp =[[10**9] *N for _ in range(N)]
    min_k_store_array = list(range(N))
    for i in range(N):
        dp[i][i] = 0
        prefix_sum[i+1] = prefix_sum[i] + books[i]
    for term in range(1,N):
        new_arr = [None]*N
        for i in range(N-term):
            j = term+i
            for k in range(min_k_store_array[i],min(min_k_store_array[i+1]+1,j)):
                if dp[i][j] > dp[i][k]+dp[k+1][j]:
                    dp[i][j] = dp[i][k]+dp[k+1][j]
                    new_arr[i] = k

            dp[i][j] += prefix_sum[j+1] - prefix_sum[i]
        min_k_store_array = new_arr
    print(dp[0][N-1])

T = int(input())
INF = float('inf')

for _ in range(T):
    N = int(input())
    arr = list(map(int,input().split()))
    result = 0
    while len(arr) >=2:
        find_idx = len(arr)-2
        for i in range(len(arr)-2):
            if arr[i] <= arr[i+2]:
                find_idx = i
                break
        a1 = arr.pop(find_idx)
        a2 = arr.pop(find_idx)
        B = a1 + a2
        arr.insert(find_idx,B)
        result += B
        B_index = find_idx
        while B_index >0 and arr[B_index-1] < arr[B_index]:
            arr[B_index],arr[B_index-1] = arr[B_index-1],arr[B_index]
            B_index -= 1

    print(result)

N, M  = map(int,input().split())
not_visited_days = [True]*(N+1)
if M:
    for k in list(map(int,input().split())):
        not_visited_days[k] = False
        

INF = float('inf')
dp = [[INF for _ in range(40)] for _ in range(105)] 

dp[0][0] = 0


for day in range(N):
    for coupon in range(37):
        if not not_visited_days[day+1]:
            dp[day+1][coupon] = min(dp[day+1][coupon],dp[day][coupon])
        dp[day+1][coupon] = min(dp[day+1][coupon],dp[day][coupon] + 10000)
        dp[day+3][coupon+1] = min(dp[day+3][coupon+1],dp[day][coupon] + 25000)
        dp[day+5][coupon+2] = min(dp[day+5][coupon+2],dp[day][coupon] + 37000)

    for coupon in range(39,2,-1):
        dp[day+1][coupon-3] = min(dp[day+1][coupon-3],dp[day][coupon])
    

print(min(dp[N]))
    
    
    

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)

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))

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')