#if defined(EMBE_DEBUG) && !defined(NDEBUG) #include "embe-debug.hpp" #else #define LOG_INDENT(...) do {} while (false) #define LOG(...) do {} while (false) #define DUMP(...) do {} while (false) #endif #include <algorithm> #include <iostream> #include <vector> using namespace std; namespace { constexpr auto mod = 1'000'000'007; int solve(vector<int> data) { sort(data.begin(), data.end()); auto biggest = data.back(); vector<int> counts(biggest + 1); counts[0] = 1; for (auto x: data) { for (int i = biggest; i >= x - 1; --i) { auto j = min(i + x, biggest); counts[j] += counts[i]; counts[j] %= mod; } } int res = mod - 1; for (auto c: counts) { res += c; res %= mod; } return res; } } int main() { iostream::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> data(n); for (auto& x: data) cin >> x; cout << solve(move(data)) << endl; return 0; }
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 51 52 53 54 | #if defined(EMBE_DEBUG) && !defined(NDEBUG) #include "embe-debug.hpp" #else #define LOG_INDENT(...) do {} while (false) #define LOG(...) do {} while (false) #define DUMP(...) do {} while (false) #endif #include <algorithm> #include <iostream> #include <vector> using namespace std; namespace { constexpr auto mod = 1'000'000'007; int solve(vector<int> data) { sort(data.begin(), data.end()); auto biggest = data.back(); vector<int> counts(biggest + 1); counts[0] = 1; for (auto x: data) { for (int i = biggest; i >= x - 1; --i) { auto j = min(i + x, biggest); counts[j] += counts[i]; counts[j] %= mod; } } int res = mod - 1; for (auto c: counts) { res += c; res %= mod; } return res; } } int main() { iostream::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> data(n); for (auto& x: data) cin >> x; cout << solve(move(data)) << endl; return 0; } |