N = int(input())

arr = []
total_person = 0 
for _ in range(N):
    town,person = map(int,input().split())
    total_person += person
    arr.append([town,person])
arr.sort()
person_list = [k[1] for k in arr]
start = 0
ends = N -1
answer = float('inf')
while start <= ends:
    mid = (start+ends)//2
    left = sum(person_list[:mid+1])
    right = total_person - left
    if left >= right:
        answer = min(arr[mid][0],answer)
        ends = mid - 1
    else:
        start = mid + 1
print(answer)

 

 

import sys
input = sys.stdin.readline

N = int(input())
total_person = 0
arr = []
for _ in range(N):
    town,person = map(int,input().split())
    total_person += person
    arr.append([town,person])

arr.sort()
left_person = 0
ind = 0
while left_person < total_person/2:
    left_person += arr[ind][1]
    ind += 1
print(arr[ind-1][0])
def TSP(ind,visited_city):
    if dp[ind][visited_city] != INF:
        return dp[ind][visited_city]
    if visited_city == (1<<N)-1:
        if arr[ind][0]:
            return arr[ind][0]
        else:
            return INF

    for next_city in range(N):
        if not (visited_city&1<<next_city) and arr[ind][next_city]:
            temp = TSP(next_city,visited_city|1<<next_city) + arr[ind][next_city]
            dp[ind][visited_city] = min(dp[ind][visited_city],temp)

    return dp[ind][visited_city]





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

INF = float('inf')
dp = [[INF]*(2**N) for _ in range(N)]

print(TSP(0,1))
T,N,D,K = map(int,input().split())

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

arr.sort()
tea_cnt = [0]*N
for ind in range(N):
    left = ind
    right = N-1
    tea_time = arr[ind]
    while left <=right:
        mid = (left+right)//2

        if arr[mid] >= tea_time+D:
            right = mid -1
        else:
            left = mid + 1
    tea_cnt[ind] = left - ind

dp = [[0]*(K+1) for _ in range(N+1)]
for idx in range(N):
    for drink_coffee in range(1,K+1):
        dp[tea_cnt[idx]+idx][drink_coffee] = max(dp[tea_cnt[idx]+idx][drink_coffee], dp[idx][drink_coffee-1]+tea_cnt[idx])
        dp[idx+1][drink_coffee] = max(dp[idx+1][drink_coffee],dp[idx][drink_coffee])
for row in dp:
    print(row)
print(max(map(max,dp)))

'알고리즘 > 백준_복기_미완료' 카테고리의 다른 글

[BOJ/백준] 2141 우체국  (0) 2021.05.02
[BOJ/백준] 2098 외판원 순회  (0) 2021.05.02
[BOJ/백준] 1949 우수 마을  (0) 2021.05.02
[BOJ/백준] 1722 순열의 순서  (0) 2021.05.02
[BOJ/백준] 1405 미친 로봇  (0) 2021.05.02
import sys

sys.setrecursionlimit(100000)
def dfs(node):
    
    if visited[node]:
        return
    visited[node] = True
    child_nodes = []
    for next_node in graph[node]:
        if not visited[next_node]:
            child_nodes.append(next_node)

    if not len(child_nodes):
        dp[node][0] = town_person[node]
        return

    for child_node in child_nodes:
        dfs(child_node)
        dp[node][0] += dp[child_node][1]
        dp[node][1] +=  max(dp[child_node][0],dp[child_node][1])
    dp[node][0] += town_person[node]





N = int(input())
town_person = [0] +list(map(int,input().split()))
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)]
# 0번 인덱스 : 참여를 했을때
# 1번 인덱스 : 참여를 안 했을때
dfs(1)

print(max(dp[1]))
from functools import lru_cache
from collections import deque
@lru_cache(maxsize=50)
def fatorial(N):
    if N == 1:
        return 1
    elif N == 2:
        return 2
    else:
        return N*fatorial(N-1)


N = int(input())

command,*arr = map(int,input().split())

patorial_cnt = []

for k in range(1,N+1):
    patorial_cnt.append(fatorial(k))
if command == 1:
    k = arr[0] - 1
    numbers = list(range(1,N+1))
    result = []
    lens = N-2
    while lens >= 0:
        copy_k = k
        ind = copy_k//patorial_cnt[lens]
        k = copy_k%patorial_cnt[lens]
        result.append(numbers.pop(ind))
        lens -= 1
    result.append(numbers.pop())
    print(*result)
else:
    numbers = list(range(1,N+1))
    result = 1
    lens = N - 2
    while arr:
        find_num = arr.pop(0)
        index = numbers.index(find_num)
        result += patorial_cnt[lens]*index
        numbers.pop(index)
        lens -= 1
    print(result)


def check(cnt,total,di):
    global result
    if cnt == arr[0]:
        temp = 1
        for k in di:
            temp *= arr[dire.index(k)+1]/100
        result += temp
        return
    else:
        cu_x,cu_y = total[-1]
        for i in range(4):
            nx = cu_x + dx[i]
            ny = cu_y + dy[i]
            if (nx,ny) not in total:
                check(cnt+1,total+[(nx,ny)],di+[dire[i]])
    


# 동 서 남 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]
dire = ['E','W','S','N']
arr = list(map(int,input().split()))
result = 0
check(0,[(0,0)],[])
print(ccnt)

 

 

def dfs(x,y,persent,cnt):
    global revers_persen,N,total
    if arr[x][y] == 1:
        revers_persen += persent
        return
    if cnt == N:
        return
    arr[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if persentlist[i]:
            dfs(nx,ny,persent*persentlist[i],cnt+1)
    arr[x][y] = 0



N,e,w,s,n = map(int,input().split())

e,w,s,n = e/100,w/100,s/100,n/100
dx = [0,0,1,-1]
dy = [1,-1,0,0]
persentlist = [e,w,s,n]
arr = [[0]*29 for _ in range(29)]

revers_persen = 0
dfs(14,14,1,0)
print(f'{1-revers_persen:.10f}')
from itertools import permutations
from collections import defaultdict

N = int(input())
alphabet = set()
total = defaultdict(int)
for _ in range(N):
    temp = list(input())
    alphabet.update(temp)
    temp.reverse()
    num = 1
    for k in temp:
        total[k] += num
        num*= 10

result = 0
alphabet = list(alphabet)

num_list = list(range(10-len(alphabet),10))
for new_nums in permutations(num_list):
    temp = 0
    ind = 0
    for key in total.keys():
        temp += total[key]*new_nums[ind]
        ind += 1
    result = max(result,temp)
        

print(result)

 

 

from itertools import permutations
from collections import defaultdict

N = int(input())
alphabet = set()
total = defaultdict(int)
for _ in range(N):
    temp = list(input())
    alphabet.update(temp)
    temp.reverse()
    num = 1
    for k in temp:
        total[k] += num
        num*= 10

result = 0
list_of_alpha =  list(total.values())
num = 9
list_of_alpha.sort(reverse=True)

for k in list_of_alpha:
    result = result + k*num
    num -= 1
print(result)

 

def belman_ford(S,E):
    INF = float('inf')
    earn_list = [INF]*N
    earn_list[S] = -benefit[S]
    for _ in range(M):
        for node in range(N):
            for next_node in bus_pay[node]:
                next_pay = bus_pay[node][next_node]
                if earn_list[next_node] > earn_list[node] + next_pay - benefit[next_node]:
                    earn_list[next_node] = earn_list[node] + next_pay - benefit[next_node]

    cycle_node = set()
    for _ in range(M):
        for node in range(N):
            for next_node in bus_pay[node]:
                next_pay = bus_pay[node][next_node]
                if earn_list[next_node] > earn_list[node] + next_pay - benefit[next_node]:
                    earn_list[next_node] = earn_list[node] + next_pay - benefit[next_node]
                    cycle_node.add(next_node)
                    cycle_node.add(node)
    if earn_list[E] == INF:
        print('gg')
    else:
        if len(cycle_node)>0:
            visted = [False]*N
            path_list = list(cycle_node)
            while path_list:
                node = path_list.pop(0)
                for next_node in bus_pay[node]:
                    if visted[next_node] == False:
                        visted[next_node] = True
                        path_list.append(next_node)
            if visted[E]:
                print('Gee')
                return
            else:
                print(-earn_list[E])
        else:
            print(-earn_list[E])



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


bus_pay = [{} for _ in range(N)]
for _ in range(M):
    a_city,b_city,pay = map(int,input().split())
    bus_pay[a_city][b_city] = min(bus_pay[a_city].get(b_city,float('inf')),pay)

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



belman_ford(start_city,end_city)

+ Recent posts