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
-
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 15:00:00, while regular practice lets you submit solutions without any constraints.
You must log in to register. - A Subset sum 2
- B Subset sum 3
- C Subset sum
- D Range Sum
- E Range Sum 2
- F Range Sum 2.py
- G Range Sum SIMD