Subset sum

Time: 1.0 s Memory: 1024 MB

Eva vill bygga ett torn för att ta foton på Sandsjön. Hon har $N$ klossar av olika höjd. För varje möjlig delmängd klossar kommer hon stapla de på höjd och klättra till toppen av tornet för att ta en bild. Hon märker dock att många av dessa bilder blir samma! Detta kanske inte är så konstigt eftersom hon alltid tar samma bild för samma tornhöjd. Hur många unika foton kommer hon ha tagit när hon är färdig?

$\includegraphics[width=0.5\textwidth ]{eva.png}$

Figure 1: Eva.

Indata

Den första raden innehåller heltalet $N$ ($1 \leq N \leq 4000$), antalet klossar. Därefter följer $N$ heltal $H_i$ ($H_i \leq 1000$), höjden på den $i$:te klossen.

Utdata

Skriv ut ett heltal: antalet unika bilder som Eva tagit när hon är färdig.

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$	$33$	$N \leq 16$
$2$	$33$	$N \leq 100$
$3$	$34$	Inga ytterligare begräsningar.

Sample Input 1	Sample Output 1
1 1	2

Sample Input 2	Sample Output 2
3 2 3 3	6

Sample Input 3	Sample Output 3
4 7 6 4 3	13

Authors: Joshua Andersson License: CC BY-SA

CCC lectures

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

You must log in to submit solutions to the problem.