Coding 공부

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

N = int(input())

dp = [[0]*10 for _ in range(N)]


temp = [-1,1]
for i in range(N):
    for j in range(10):
        if i == N-1:
            if j == 0:
                continue
        if i == 0:
            dp[0][j] = 1
        else:
            for k in temp:
                nx = j+k
                if 0<=nx<10:
                    dp[i][j] += dp[i-1][j+k]

            
print(sum(dp[N-1])%1000000000)

a = """\    /\\
 )  ( ')
(  /  )
 \\(__)|
"""
print(a)

def check(num):
    visited_numbers = set()
    visited_numbers.add(num)
    if visited[num] == 1:
        return True
    elif visited[num] == 0:
        return False

    while num >= 0:
        temp = 0
        copy_num = num
        while copy_num>0:
            calc_num = copy_num%10
            next_num = copy_num//10
            temp = temp + calc_num**2
            copy_num = next_num
        num = temp
        if temp == 1:
            for vi_num in visited_numbers:
                visited[vi_num] = 1
            return True
        elif temp not in visited_numbers:
            visited_numbers.add(temp)
        else:
            for vi_num in visited_numbers:
                visited[vi_num] = 0
            return False
        


def find_prime_number(N):
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False
    prime_list = []
    for num in range(2,N+1):
        if numbers[num]:
            prime_list.append(num)
            for not_prime in range(num+num,N+1,num):
                numbers[not_prime] = False
    return prime_list




N = int(input())


prime_numbers = find_prime_number(N)

visited = [-1]*1000001
result = []

for num in prime_numbers:
    if check(num):
        result.append(num)
for row in result:
    print(row)

def find_arr(arr):
    global result
    for bit_mask in range(2**8):
        copy_arr = [row[:] for row in arr]
        change_bit = str(bin(bit_mask))[2:].count('1')
        if result < change_bit:
            continue
        for row in range(3):
            if bit_mask & (1<<row):
                for col in range(3):
                    copy_arr[row][col] = (copy_arr[row][col]+1)%2

        for col in range(3):
            if bit_mask & (1<<(col+3)):
                for row in range(3):
                    copy_arr[row][col] = (copy_arr[row][col]+1)%2


        if bit_mask & (1<<6):
            for row in range(3):
                copy_arr[row][row] = (copy_arr[row][row]+1)%2

        if bit_mask & (1<<7):
            for row in range(3):
                copy_arr[row][2-row] = (copy_arr[row][2-row]+1)%2

        sum_temp = sum(list(map(sum,copy_arr)))
        if sum_temp == 9 or sum_temp == 0:
            result = change_bit






T = int(input())



for tc in range(T):
    arr = []
    result = float('inf')
    for _ in range(3):
        s = list(input().split())
        for i in range(3):
            if s[i] == 'T':
                s[i] = 1
            else:
                s[i] = 0
        arr.append(s)
    
    cnt = 0

    find_arr(arr)
    print(-1 if result == float('inf') else result)

from collections import Counter

def move_robot(mad_ro,ro):
    new_robot = []

    for mad_x,mad_y in mad_ro:
        ro_distance = float('inf')
        ro_direction = -1
        for i in range(9):
            mad_nx = mad_x + dx[i]
            mad_ny = mad_y + dy[i]
            if 0<= mad_nx < R and 0<= mad_ny <C:
                distance = abs(mad_nx - ro[0]) + abs(mad_ny-ro[1])
                if ro_distance > distance:
                    ro_distance = distance
                    ro_direction = i

        new_x = mad_x + dx[ro_direction]
        new_y = mad_y + dy[ro_direction]
        new_robot.append((new_x,new_y))

    return new_robot
    
def bomb_robot(mad_ro):
    count_mad_ro = Counter(mad_ro)
    new_mad_ro = set()
    for key,value in count_mad_ro.items():
        if value == 1:
            new_mad_ro.add(key)
    return new_mad_ro




R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]

mad_robots = set()
robot = (0,0)
for i in range(R):
    for j in range(C):
        if arr[i][j] == 'R':
            mad_robots.add((i,j))
            arr[i][j] = '.'
        elif arr[i][j] == 'I':
            robot = (i,j)
            arr[i][j] = '.'

command = list(map(lambda x : x-1, map(int,list(input()))))
dx = [1,1,1,0,0,0,-1,-1,-1]
dy = [-1,0,1,-1,0,1,-1,0,1]
flag = False
answer = 0
for time in range(len(command)):
    x,y = robot
    nx = x + dx[command[time]]
    ny = y + dy[command[time]]
    if (nx,ny) in mad_robots:
        flag =  True
        answer = time + 1
        break
    robot = (nx,ny)
    mad_robots = move_robot(mad_robots,robot)

    if robot in mad_robots:
        flag = True
        answer = time + 1
        break
    mad_robots = bomb_robot(mad_robots)


if flag:
    print(f'kraj {answer}')
else:
    arr[robot[0]][robot[1]] = 'I'
    for mad in mad_robots:
        arr[mad[0]][mad[1]] = 'R'

    for row in arr:
        print(''.join(row))

N,M = map(int,input().split())
INF= float('inf')
dp = [INF]*(M+1)
apps_memory = list(map(int,input().split()))
apps_value = list(map(int,input().split()))
for i in range(N):
    memory,value = apps_memory[i],apps_value[i]
    for k in range(M,-1,-1):
        if k == 0:
            if memory >=M:
                memory = M
            dp[memory] = min(dp[memory],value)
        else:
            if dp[k]:
                num_memory = k + memory
                if num_memory >=M:
                    dp[M] = min(dp[M],dp[k]+value)
                else:
                    dp[num_memory] = min(dp[num_memory],dp[k]+value)
print(dp[M])

N,M = map(int,input().split())
INF= float('inf')

apps_memory = list(map(int,input().split()))
apps_value = list(map(int,input().split()))
total_sum = sum(apps_value)

dp = [0]*(total_sum+1)
result = INF
for i in range(N):
    for j in range(total_sum,apps_value[i]-1,-1):
        if j - apps_value[i] >=0:
            dp[j] = max(dp[j],dp[j-apps_value[i]]+apps_memory[i])
        if dp[j] >= M:
            result = min(j,result)

print(result)