1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// cuk-cukierki.cpp : Ten plik zawiera funkcję „main”. W nim rozpoczyna się i kończy wykonywanie programu.
//

#include <iostream>
#include <algorithm>

constexpr int MAXN = 5007;
constexpr long long MOD = 1000000007;
//constexpr int MAXS = MAXN * MAXN;

int t[MAXN];
long long dp[MAXN];

int main()
{
    int n;
	long long answ = 0;
    std::cin >> n;
	for (size_t i = 1; i <= n; i++)
	{
		std::cin >> t[i];
	}
	std::sort(t, t + n + 1);
	dp[0] = 1;
	for (size_t i = 1; i <= n; i++)
	{
		for (int j = MAXN-1; j >= t[i]-1; j--)
		{
			dp[std::min(MAXN - 1, t[i] + j)] += dp[j];
			dp[std::min(MAXN - 1, t[i] + j)] %= MOD;
		}
	}
	for (size_t i = 1; i <= MAXN; i++)
	{
		answ += dp[i];
		answ %= MOD;
	}
	std::cout << answ << '\n';
}

// Uruchomienie programu: Ctrl + F5 lub menu Debugowanie > Uruchom bez debugowania
// Debugowanie programu: F5 lub menu Debugowanie > Rozpocznij debugowanie

// Porady dotyczące rozpoczynania pracy:
//   1. Użyj okna Eksploratora rozwiązań, aby dodać pliki i zarządzać nimi
//   2. Użyj okna programu Team Explorer, aby nawiązać połączenie z kontrolą źródła
//   3. Użyj okna Dane wyjściowe, aby sprawdzić dane wyjściowe kompilacji i inne komunikaty
//   4. Użyj okna Lista błędów, aby zobaczyć błędy
//   5. Wybierz pozycję Projekt > Dodaj nowy element, aby utworzyć nowe pliki kodu, lub wybierz pozycję Projekt > Dodaj istniejący element, aby dodać istniejące pliku kodu do projektu
//   6. Aby w przyszłości ponownie otworzyć ten projekt, przejdź do pozycji Plik > Otwórz > Projekt i wybierz plik sln