Stacking boxes - MarisaOJ: Marisa Online Judge

You are given

n

$n$ boxes, each with a weight denoted by

W_{1}, W_{2}, \dots, W_{n}

$W_1, W_2, \ldots, W_n$ . These boxes can be stacked on top of each other, and each box

i

$i$ has a weight capacity denoted by

C_{i}

$C_i$ , indicating the maximum weight it can withstand when other boxes are placed on top of it. Your task is to determine the maximum number of boxes that can be stacked together while ensuring that the weight capacity of each box is not exceeded. ### Input - The first line contains an integer

n

$n$ . - The second line contains

n

$n$ integer

W_{i}

$W_i$ . - The third line contains

n

$n$ integer

C_{i}

$C_i$ . ### Output - Print an integer, the maximum number of boxes can be stacked. ### Constraints -

1 \leq n \leq 5000

$1 \le n \le 5000$ . -

1 \leq W_{i} \leq 10^{10}

$1 \le W_i \le 10^{10}$ . -

1 \leq C_{i} \leq 10^{10}

$1 \le C_i \le 10^{10}$ . ### Example Input:

31120301110010

$3 11 20 30 11 100 10$

Output:

2

$2$

Introduction to Dynamic Programming (Part two)
	Sake game
	Coins
	Coins 2
	Game on array
	Longest increasing subsequence 2
	Convolution
	Regular bracket sequence
	Faulty addition
	Weird bank
	Delete operation
	Palindromize
	Color ribbon
	Unique subsequences
	Unique subsequences 2
	Cow exhibition
	Knapsack 3
	Compressing array
	Regular bracket sequence 2
	Maximum path 3
	Concating substring
	Soil
	Stacking boxes
	String transformation
	Palindromic quadruple
	Finding teammates

Topic

Sorting

Greedy

Dynamic Programming

Rating

1700

Solution (0)

Solution