Knapsack - MarisaOJ: Marisa Online Judge

Given

n

$n$ objects, where the

i

$i$ -th object has a weight of

w_{i}

$w_i$ . For each weight

k

$k$ from

1

$1$ to

T

$T$ , determine whether there is a way to select some objects out of the

n

$n$ objects such that their total weight is

k

$k$ . ### Input - The first line contains two integers

n

$n$ and

T

$T$ . - The second line contains

n

$n$ integers

w_{i}

$w_i$ . ### Output - Print a binary string of length

T

$T$ , where the

i

$i$ -th character is

0

$0$ or

1

$1$ indicating whether it's impossible or possible to achieve weight

i

$i$ . ### Constraints -

1 \leq n, T, \sum w_{i} \leq 10^{6}

$1 \leq n, T, \sum{w_i} \leq 10^6$ . ### Example Input:

52043344

$5 20 4 3 3 4 4$

Output:

00110111011101100100

$00110111011101100100$

Square root decomposition
	Frequency
	Tree query
	Inversions query
	Nearest vertex
	Dominating color
	String occurences 3
	Inversions query 2
	Pair
	Sparse update
	Tree
	Range query
	String concatenation
	Subarray distance
	Chameleon
	Knapsack
	Bit counting
	Subsequence queries
	Sub-subsequence
	Delete numbers
	Mode
	Marisa is happy
	Inversions query 3
	Upperbound
	23 path
	Yet another square root decomposition problem
	Marisa plays poker
	Wonderful world

Topic

Dynamic Programming

Rating

2000

Solution (1)

Solution