Subset sum 3

Time: 1.0 s Memory: 1024 MB

Givet är $N$ positiva heltal. Hitta den delmängd av dessa heltal som har störst summa mindre än eller lika med $T$.

Indata

Den första raden innehåller två heltal $N, T$ ($1 \leq N \leq 10^5, 1 \leq T \leq 1000*N$). Därefter följer $N$ heltal $A_i$. Alla $A_i$ är slumpmässigt valda mellan $0$ och $1000$.

Utdata

Skriv ut ett heltal: den största summan mindre än eller lika med $T$ man kan få av en delmängd.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp	Poäng	Gränser
$1$	$10$	$N \leq 100$
$2$	$30$	$N \leq 4000$
$3$	$30$	$N \leq 10000$
$4$	$30$	Inga ytterligare begräsningar.

Sample Input 1	Sample Output 1
4 15 7 6 4 3	14

Authors: Joshua Andersson License: CC BY-SA

Subset-sum

To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.

You must log in to register.
1 Subset sum
2 Subset sum 2
3 Subset sum 3
4 Subset sum 4
5 Subset sum 5

You must log in to submit solutions to the problem.