Problem:


Score : 700 points

Problem Statement

In the final of CODE FESTIVAL in some year, there are N participants.
The height and power of Participant i is H_i and P_i, respectively.

Ringo is hosting a game of stacking zabuton (cushions).

The participants will line up in a row in some order, and they will in turn try to add zabuton to the stack of zabuton.
Initially, the stack is empty.
When it is Participant i's turn, if there are H_i or less zabuton already stacked, he/she will add exactly P_i zabuton to the stack. Otherwise, he/she will give up and do nothing.

Ringo wants to maximize the number of participants who can add zabuton to the stack.
How many participants can add zabuton to the stack in the optimal order of participants?

Constraints

1 \leq N \leq 5000

0 \leq H_i \leq 10^9

1 \leq P_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
H_1 P_1
H_2 P_2
:
H_N P_N

Output

Print the maximum number of participants who can add zabuton to the stack.

Sample Input 1

3
0 2
1 3
3 4

Sample Output 1

2

When the participants line up in the same order as the input, Participants 1 and 3 will be able to add zabuton.

On the other hand, there is no order such that all three participants can add zabuton. Thus, the answer is 2.

Sample Input 2

3
2 4
3 1
4 1

Sample Output 2

3

When the participants line up in the order 2, 3, 1, all of them will be able to add zabuton.

Sample Input 3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

Sample Output 3

5



Sample input:
3
0 2
1 3
3 4


Sample output:
2

Submission status: Wrong Answer

Solution code:
import bisect

N=int(input())
hito=[]
for i in range(N):
    h,p=map(int,input().split())
    hito.append((h+p,h,p))

hito.sort()
print(hito)
data=[0]
for i in range(0,N):
    gomi,h,p=hito[i]
    for j in range(len(data)-1,-1,-1):
        if j==len(data)-1:
            if h>=data[-1]:
                data.append(data[-1]+p)
            if h>=data[j-1] and j!=0:
                data[j]=min(data[j],data[j-1]+p)
        else:
            if h>=data[j-1] and j!=0:
                data[j]=min(data[j],data[j-1]+p)
    

print(len(data)-1)

Submission status: Wrong Answer

Solution code:
import bisect

N=int(input())
hito=[]
for i in range(N):
    h,p=map(int,input().split())
    hito.append((h+p,h,p))

hito.sort()
data=[0]
for i in range(0,N):
    gomi,h,p=hito[i]
    id=bisect.bisect_right(data,h)
    if id==len(data):
        data.append(data[-1]+p)
    else:
        data[id]=min(data[id-1]+p,data[id])

print(len(data)-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
hp = [list(map(int,input().split())) for i in range(n)]
hp.sort(key = lambda x:x[0]+x[1])
dp = [[10**18 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
  dp[i] = dp[i-1][:]
  h,p = hp[i-1]
  for j in range(1,i+1):
    if dp[i-1][j-1] <= h:
      dp[i][j] = min(dp[i][j],dp[i-1][j-1]+p)
for i in range(n+1):
  if dp[-1][i] == 10**18:
    print(i-1)
    break

Submission status: Wrong Answer

Solution code:
"""
H+Pでソートしてから、dpする。
◆H+Pでソートする理由
直感的に考える。
「余裕がない人」から先に積んだ方がいい。
余裕は何で決まるか？
それはその人のHと、他の人のPである。

S枚積まれた状態で、身長H1,力P1のA君と身長H2,力P2のB君、二人の人間がいる。どちらを先に積ませるべきか？
という問題を考える。
このとき、もしS+P1<=H2ならA君に先に積ませて問題ない。
これを変形すると、S<=H2-P1となる。
このH2-P1こそがB君にとっての「余裕」である。
余裕が大きければ大きいほど、より大きなSに対応できる。すなわち、後ろの方でも問題ないということになる。

では、余裕の程度の昇順に並び変えることと、H+Pの昇順で並び変えることが同義になるのはなぜか。
また先ほどのA君とB君の例に立ち返る。
A君の余裕はH1-P2で表せる。B君の余裕はH2-P1で表せる。余裕の程度を比較するので、
H1 - P2 < H2 - P1 ならB君の方が余裕が大きいので、B君が後になる。
上記の不等式を変形すると、H1 + P1 < H2 + P2となる。よって、H+Pの大きい方が余裕が大きいことがわかる。
これが余裕の程度の昇順に並び変えることと、H+Pの昇順で並び変えることが同義になる理由である。
"""
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

inf = 10**9+1
dp = [[inf]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1] <= h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != inf:
        print(j)
        break

Submission status: Wrong Answer

Solution code:
"""
H+Pでソートしてから、dpする。
◆H+Pでソートする理由
直感的に考える。
「余裕がない人」から先に積んだ方がいい。
余裕は何で決まるか？
それはその人のHと、他の人のPである。

S枚積まれた状態で、身長H1,力P1のA君と身長H2,力P2のB君、二人の人間がいる。どちらを先に積ませるべきか？
という問題を考える。
このとき、もしS+P1<=H2ならA君に先に積ませて問題ない。
これを変形すると、S<=H2-P1となる。
このH2-P1こそがB君にとっての「余裕」である。
余裕が大きければ大きいほど、より大きなSに対応できる。すなわち、後ろの方でも問題ないということになる。

では、余裕の程度の昇順に並び変えることと、H+Pの昇順で並び変えることが同義になるのはなぜか。
また先ほどのA君とB君の例に立ち返る。
A君の余裕はH1-P2で表せる。B君の余裕はH2-P1で表せる。余裕の程度を比較するので、
H1 - P2 < H2 - P1 ならB君の方が余裕が大きいので、B君が後になる。
上記の不等式を変形すると、H1 + P1 < H2 + P2となる。よって、H+Pの大きい方が余裕が大きいことがわかる。
これが余裕の程度の昇順に並び変えることと、H+Pの昇順で並び変えることが同義になる理由である。
"""
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

dp = [[0,0]for _ in range(N)]
dp[0] = [men[0][1],1]
for i in range(1,N):
    h,p = men[i][0],men[i][1]
    if dp[i-1][0] <= h:
        dp[i] = [dp[i-1][0]+p,dp[i-1][1]+1]
    else:
        dp[i] = dp[i-1][:]

print(dp[-1][1])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from operator import itemgetter
    import bisect
    input = sys.stdin.readline

    N = int(input())
    HP = []
    for i in range(N):
        h, p = map(int, input().split())
        HP.append((h, p, h+p))
    HP.sort(key=itemgetter(2))

    dp = [0]
    L = 1
    for i in range(N):
        h, p, _ = HP[i]
        j = bisect.bisect_left(dp, h+1)
        if j == L:
            dp.append(dp[-1] + p)
            L += 1
        else:
            dp[j] = min(dp[j], dp[j-1] + p)
    print(L-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from operator import itemgetter
    import bisect
    input = sys.stdin.readline

    N = int(input())
    HP = []
    for i in range(N):
        h, p = map(int, input().split())
        HP.append((h, p, h+p))
    HP.sort(key=itemgetter(2))

    dp = [0]
    L = 1
    for i in range(N):
        h, p, _ = HP[i]
        j = bisect.bisect_right(dp, h)
        if j == L:
            dp.append(dp[-1] + p)
            L += 1
        else:
            dp[j] = min(dp[j], dp[j-1] + p)
    print(L-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=[list(map(int,input().split())) for _ in [0]*n]
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    rank=[0]*n
    for i in range(n):
        for j in range(i+1,n):
            k=hp[i][0]-hp[j][1]-hp[j][0]+hp[i][1]
            if k<0:
                rank[j]+=2
            elif k>0:
                rank[i]+=2
            else:
                rank[j]+=1
                rank[i]+=1
    #print(rank)
    rank=sorted([[j,i] for i,j in enumerate(rank)])
    hp=[hp[j] for i,j in rank]
    #print(hp)
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=[list(map(int,input().split())) for _ in [0]*n]
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    rank=[0]*n
    for i in range(n):
        for j in range(i,n):
            k=hp[i][0]-hp[j][1]-hp[j][0]+hp[i][1]
            if k<0:
                rank[j]+=2
            elif k>0:
                rank[i]+=2
            else:
                rank[j]+=1
                rank[i]+=1
    #print(rank)
    rank=sorted([[j,i] for i,j in enumerate(rank)])
    hp=[hp[j] for i,j in rank]
    #print(hp)
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=[list(map(int,input().split())) for _ in [0]*n]
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    rank=[0]*n
    for i in range(n):
        for j in range(i,n):
            k=hp[i][0]-hp[j][1]-hp[j][0]+hp[i][1]
            if k<0:
                rank[j]+=1
            elif k>0:
                rank[i]+=1
    #print(rank)
    rank=sorted([[j,i] for i,j in enumerate(rank)])
    hp=[hp[j] for i,j in rank]
    #print(hp)
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=[list(map(int,input().split())) for _ in [0]*n]
    dp=[10**9+1]*(n+1)
    dp[0]=0
    rank=[0]*n
    for i in range(n):
        for j in range(i,n):
            if hp[i][0]-hp[j][1]<hp[j][0]-hp[i][1]:
                rank[j]+=1
    rank=sorted([[j,i] for i,j in enumerate(rank)])
    hp=[hp[j] for i,j in rank]
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:(x[1],x[0]))
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:(min(x),sum(x)))
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:(max(x),sum(x)))
    #print(hp)
    dp=[10**9+1]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:(x[1],x[0]))
    dp=[10**9+1]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=dp[k]+p
    for i in range(n,-1,-1):
        if dp[i]!=10**9+1:
            print(i)
            break
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []

for i in range(N):
    A.append(list(map(int, input().split())))

A = sorted(A, key = lambda x:x[0])
A = sorted(A, key = lambda x:x[1])

h = 0
ans = 0
for i in range(N):
    if h <= A[i][0]:
        h += A[i][1]
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], x[1]))
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				if dp[j][0] + men[i-1][1] < dp[j][0]:
					dp[i][0] = dp[j][0] + men[i-1][1]
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], x[1]))
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				dp[i][0] = min(dp[i][0], dp[j][0] + men[i-1][1])
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], x[0]))
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				dp[i][0] = min(dp[i][0], dp[j][0] + men[i-1][1])
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: x[0]+x[1])
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				dp[i][0] = min(dp[i][0], dp[j][0] + men[i-1][1])
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[1], x[0]))
dp = [[0, 0] for _ in range(n+1)]
for i in range(1, n+1):
	for j in range(i):
		if dp[j][0] <= men[i-1][0]:
			if dp[j][1]+1 == dp[i][1]:
				dp[i][0] = min(dp[i][0], dp[j][0] + men[i-1][1])
			elif dp[j][1]+1 > dp[i][1]:
				dp[i][1] = dp[j][1]+1
				dp[i][0] = dp[j][0] + men[i-1][1]
ans = 0
for i in range(1, n+1):
	ans = max(ans, dp[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

class Boxes:

    def __init__(self,str,weight):
        self.str=str
        self.weight=weight
    
    def __repr__(self):
        return '({} , {})'.format(self.str,self.weight)

def box_cmp(box_a,box_b):

    if(box_a.str+box_a.weight > box_b.str+box_b.weight):
        return -1
    elif(box_a.str+box_a.weight < box_b.str+box_b.weight):
        return 1
    else:
        return 0

def get_max_seq(index,weight_sum,count):
    res=-1
    if(index<0):
        return count
    
    if(boxes[index].str>=weight_sum):
        res=get_max_seq(index-1,weight_sum+boxes[index].weight,count+1)

    res=max(res,get_max_seq(index-1,weight_sum,count))
    return res

def dyna(boxes,N):
    # print('boxes: ',boxes)
    INF=int(pow(2,64))
    dp=[INF]*(N+1)
    dp[0]=0
    # print('dp: ',dp)

    for  i in range(0,N):
        for j in range(i,-1,-1):

            if(dp[j]<=boxes[i].str):
                dp[j+1]=min(dp[j+1],dp[j] + boxes[i].weight)

    # print('dp: ',dp)

    for i in range(N,-1,-1):
        if(dp[i]!=INF):
            return i
    

# b_o=[(1,3),(3,4),(2,3),(5,6),(3,5),(8,7),(4,6)]
#boxes= [ Boxes(x[0],x[1]) for x in b_o]

boxes = []
N=int(input())
for _ in range(N):
    a=[ int(x) for x in input().split()]
    boxes.append(Boxes(a[0],a[1]))


# print('input len: ',len(boxes))
# print(boxes)
boxes.sort(key=cmp_to_key(box_cmp),reverse=False)
# print(boxes)
# print(get_max_seq(N-1,0,0))
print(dyna(boxes,N))
# INF=int(pow(2,64))

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

class Boxes:

    def __init__(self,str,weight):
        self.str=str
        self.weight=weight
    
    def __repr__(self):
        return '({} , {})'.format(self.str,self.weight)

def box_cmp(box_a,box_b):

    if(box_a.str+box_a.weight > box_b.str+box_b.weight):
        return -1
    elif(box_a.str+box_a.weight < box_b.str+box_b.weight):
        return 1
    else:
        return 0

def get_max_seq(index,weight_sum,count):
    res=-1
    if(index<0):
        return count
    
    if(boxes[index].str>=weight_sum):
        res=get_max_seq(index-1,weight_sum+boxes[index].weight,count+1)

    res=max(res,get_max_seq(index-1,weight_sum,count))
    return res

def dyna(boxes,N):
    # print('boxes: ',boxes)
    INF=int(1e10+7)
    dp=[INF]*(N+1)
    dp[0]=0
    # print('dp: ',dp)

    for  i in range(0,N):
        for j in range(i,-1,-1):

            if(dp[j]<=boxes[i].str):
                dp[j+1]=min(dp[j+1],dp[j] + boxes[i].weight)

    # print('dp: ',dp)

    for i in range(N,-1,-1):
        if(dp[i]!=INF):
            return i
    

# b_o=[(1,3),(3,4),(2,3),(5,6),(3,5),(8,7),(4,6)]
#boxes= [ Boxes(x[0],x[1]) for x in b_o]

boxes = []
N=int(input())
for _ in range(N):
    a=[ int(x) for x in input().split()]
    boxes.append(Boxes(a[0],a[1]))


# print('input len: ',len(boxes))
# print(boxes)
boxes.sort(key=cmp_to_key(box_cmp),reverse=False)
# print(boxes)
# print(get_max_seq(N-1,0,0))
print(dyna(boxes,N))

Submission status: Wrong Answer

Solution code:
N = int(input())
Q = [list(map(int, input().split())) for i in range(N)]
Q.sort(key=lambda x: x[1])
INF = 10**18
dp = [INF]*(N+1)
dp[0] = 0
for a, b in Q:
    for j in range(N-1, -1, -1):
        if dp[j] <= b-a and dp[j] + a <= dp[j+1]:
            dp[j+1] = dp[j] + a
ans = 0
for i in range(N+1):
    if dp[i] < INF:
        ans = i
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

HP= [list(map(int,input().split()))+[_index] for _index in range(N)]
HP.sort()

HP2 = list(HP)
HP2.sort(key=lambda x:(x[1],x[0]))
#if not HP[-1][0]+HP[-1][1] == max(h+p for h,p in HP):
#    raise

def check(_res):
    """
    >>> check([(9, 1), (0, 1)])
    False
    :param _res:
    :return:
    """
    tmp_val = 0
    for h, p, *_ in _res:
        if (tmp_val > h):
            return False
        tmp_val += p

    return True

#print(HP2)
res =[]
for h,p,index in HP2:
   def can_insert(h,p,i):
        _res =list(res)
        _res.insert(i,(h,p))
        return check(_res)
   for i in reversed(range(len(res)+1)):
        if can_insert(h,p,i):
            res.insert(i,(h,p))
            break
    #else:
    #    break

#for h,p,index in HP:

print(len(res))

Submission status: Wrong Answer

Solution code:
N = int(input())

HP= [list(map(int,input().split()))+[_index] for _index in range(N)]
HP.sort()

HP2 = list(HP)
HP2.sort(key=lambda x:(x[1],-x[0]))
#if not HP[-1][0]+HP[-1][1] == max(h+p for h,p in HP):
#    raise

def check(_res):
    """
    >>> check([(9, 1), (0, 1)])
    False
    :param _res:
    :return:
    """
    tmp_val = 0
    for h, p, *_ in _res:
        if (tmp_val > h):
            return False
        tmp_val += p

    return True

#print(HP2)
res =[]
for h,p,index in HP2:
   def can_insert(h,p,i):
        _res =list(res)
        _res.insert(i,(h,p))
        return check(_res)
   for i in reversed(range(len(res)+1)):
        if can_insert(h,p,i):
            res.insert(i,(h,p))
            break
    #else:
    #    break

print(len(res))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

#if not HP[-1][0]+HP[-1][1] == max(h+p for h,p in HP):
#    raise


def seach(n):
    max_kouho= []
    max_val =-1
    for i in range(N-1,-1,-1):
        if i in used:
            continue
        h,p= HP[i]
        if h<max_val:break
        
        tmp_val = min(n-p,h)
        if tmp_val>max_val:
            max_kouho = [i]
            max_val=tmp_val
        elif tmp_val==max_val:
            max_kouho.append(i)
    return max_val,max_kouho


used = set([len(HP)-1])
next_val =HP[-1][0]
while next_val>0:
    max_val ,kouho = seach(next_val)

    #print(max_val)
    #print(list(HP[i] for i in kouho))
    if max_val == -1:
        break

    elif len(kouho) >=1:
        next_val=max_val
        used.add(kouho[0])

print(len(used))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

#if not HP[-1][0]+HP[-1][1] == max(h+p for h,p in HP):
#    raise


def seach(n):
    max_kouho= []
    max_val =-1
    for i in range(N):
        if i in used:
            continue
        h,p= HP[i]
        tmp_val = min(n-p,h)
        if tmp_val>max_val:
            max_kouho = [i]
            max_val=tmp_val
        elif tmp_val==max_val:
            max_kouho.append(i)
    return max_val,max_kouho


used = set([len(HP)-1])
next_val =HP[-1][0]
while next_val>0:
    max_val ,kouho = seach(next_val)

    #print(max_val)
    #print(list(HP[i] for i in kouho))
    if max_val == -1:
        break

    elif len(kouho) >=1:
        next_val=max_val
        used.add(kouho[0])

print(len(used))

Submission status: Wrong Answer

Solution code:
from bisect import*
N = int(input())
P = []

for i in range(N):
    h, p = map(int, input().split())
    P.append((h+p, h, p))
P.sort()

dp = [10**18]*(N+1)
dp[0] = 0
for i in range(N):
    k, h, p = P[i]
    idx = bisect(dp, h)
    dp[idx] = min(dp[idx-1]+p, dp[idx])
    #print(idx)
    #print(dp[:idx+1])
print(bisect(dp, 10**17)-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: x[0]+x[1])
#dp[i][j] -> i人目まで見る。j人積むときの、座布団の枚数の最小値
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
ans = 0
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    h,p = HP[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1]<=h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
            ans = max(ans,j)
        else:
            dp[i][j] = dp[i-1][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j] -> i人目までみる。j人が座布団を積むときの、最小の座布団の枚数
"""
N = int(input())
men = []
for _ in range(N):
    h,p=map(int,input().split())
    men.append((h,p))

men.sort(key=lambda x: sum(x))
ceil = max(men,key=lambda x: x[0])[0]+1
dp = [[float("INF")for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(1,N+1):
    h,p = men[i-1][0],men[i-1][1]
    for j in range(1,i+1):
        if dp[i-1][j-1] <= h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]
        
for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
men = []
hCeil = 0
for _ in range(N):
    h,p = map(int,input().split())
    men.append((h+p,h,p))
    hCeil = max(hCeil,h)
men.sort()
hCeil += 1
"""
dp[i][j][0] -> i人目までみる&j人が積むときの最小枚数
dp[i][j][1] -> 積んだかどうかのフラグ
"""
dp = [[(hCeil,0) for i in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = (0,1)
for i in range(1,N+1):
    h,p = men[i-1][1],men[i-1][2]
    for j in range(1,i+1):
        if dp[i-1][j-1][0]<=h:
            nxP = min(dp[i-1][j][0],dp[i-1][j-1][0]+p)
            dp[i][j] = (nxP,1)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j][1] != 0:
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

dp = [[float("INF")]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1] <= h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = sorted((list(map(int, input().split()))
            for _ in range(N)), key=lambda x: x[0]+x[1])
inf = 10**18
dp = [0] + [inf]*N

for i, (h, p) in enumerate(a):
    for j in range(i, -1, -1):
        if dp[j] <= h and dp[j+1] > dp[j] + p:
            dp[j+1] = dp[j] + p

for i in range(N, -1, -1):
    if dp[i] < inf:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
HP = [tuple(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: sum(x))

INF = float('inf')
dp = [[INF]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
maxj = 0
for i,(h,p) in enumerate(HP):
	for j in range(maxj,-1,-1):
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
		if dp[i][j] <= h:
			dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + p)
			if j == maxj:
				maxj += 1
print(maxj)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [tuple(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	dp[i+1][0] = 0
	for j in range(1, i+2):
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
		if dp[i][j-1] <= men[i][0]:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j-1] + men[i][1])

#print(dp)
for i in range(n+1):
	if dp[n][i] < INF:
		ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	dp[i+1][0] = 0
	for j in range(1, i+2):
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
		if dp[i][j-1] <= men[i][0]:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j-1] + men[i][1])

#print(dp)
for i in range(n+1):
	if dp[n][i] < INF:
		ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = lambda x: x[0] + x[1])
INF = 1<<64

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp += [INF]
    for j in range(i+1, 0, -1):
        if dp[j-1] > hi:
            continue
        dp[j] = min(dp[j], dp[j-1]+pi)
for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = lambda x: x[0] + x[1])
INF = 1<<64

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp2 = dp[:] + [INF]
    for j in range(i+1):
        if dp[j] > hi:
            break
        dp2[j+1] = min(dp2[j+1], dp[j]+pi)

    dp = dp2[:]

for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = sum)
INF = 10**18+3

dp = [0]
for i in range(N):
    hi, pi = HP[i]
    dp2 = dp[:] + [INF]
    for j in range(i+1):
        if dp[j] > hi:
            break
        dp2[j+1] = min(dp2[j+1], dp[j]+pi)

    dp = dp2[:]

for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N =  int(readline())
HP = [tuple(map(int, readline().split())) for _ in range(N)]
HP.sort(key = sum)
INF = 10**18+3

dp = [INF]*(N+1)
dp[0] = 0

for i in range(N):
    hi, pi = HP[i]
    dp2 = dp[:]
    for j in range(N):
        if dp[j] > hi:
            break
        dp2[j+1] = min(dp2[j+1], dp[j]+pi)

    dp = dp2[:]

for ans in range(N+1):
    if dp[ans] == INF:
        ans -= 1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  h,p = list(map(int, input().split()))
  A.append([h+p,h,p])
  
A.sort()

# N人積んだ時の最小の高さH
dp = [-1 for i in range(N+1)]
dp[0] = 0

for i in range(N):
  _,h,p = A[i]
  for j in range(N, 0, -1):
    ## まだj-1人積んだことがない
    if dp[j-1] < 0:
      continue
    ## 高すぎてつめない
    if dp[j-1] > h:
      continue
    if dp[j] < 0:
      dp[j] = dp[j-1] + p
    else:
      dp[j] = min(dp[j], dp[j-1] + p)
    
for i in range(N+1):
  if dp[i] < 0:
    print(i-1)
    exit(0)

print(N)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n = int(input())
    hp = sorted([tuple(map(int, input().split()))
                 for _ in [0]*n], key=lambda x: x[0]+x[1])
    dp = [10**10]*(n+1)
    dp[0] = 0
    for c, (h, p) in enumerate(hp):
        for k in range(c, -1, -1):
            if dp[k] <= h:
                dp[k+1] = min(dp[k+1], dp[k]+p)
    for i in range(n, -1, -1):
        if dp[i] != 10**10:
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n = int(input())
    hp = sorted([tuple(map(int, input().split()))
                 for _ in [0]*n], key=lambda x: sum(x))
    dp = [10**10]*(n+1)
    dp[0] = 0
    for c, (h, p) in enumerate(hp):
        for k in range(c, -1, -1):
            if dp[k] <= h:
                dp[k+1] = min(dp[k+1], dp[k]+p)
    for i in range(n, -1, -1):
        if dp[i] != 10**10:
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()