#include <iostream> #include <vector> #include <algorithm> typedef long long int ll; int main() { int n; std::cin>>n; std::vector<int> v(n); for(int i=0;i<n;++i) std::cin>>v[i]; std::sort(v.begin(),v.end()); constexpr int c_max=5000; constexpr ll c_mod=1000*1000*1000+7; std::vector<ll> m(c_max*c_max+1,0); m[0]=1; int top=0; for(int vi:v) { int start=vi-1; for(int i=top;i>=start;--i) if(m[i]) m[i+vi]=(m[i]+m[i+vi])%c_mod; if(top>=start) top+=vi; } ll res=-1; for(int x:m) res=(res+x)%c_mod; std::cout<<res; 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 | #include <iostream> #include <vector> #include <algorithm> typedef long long int ll; int main() { int n; std::cin>>n; std::vector<int> v(n); for(int i=0;i<n;++i) std::cin>>v[i]; std::sort(v.begin(),v.end()); constexpr int c_max=5000; constexpr ll c_mod=1000*1000*1000+7; std::vector<ll> m(c_max*c_max+1,0); m[0]=1; int top=0; for(int vi:v) { int start=vi-1; for(int i=top;i>=start;--i) if(m[i]) m[i+vi]=(m[i]+m[i+vi])%c_mod; if(top>=start) top+=vi; } ll res=-1; for(int x:m) res=(res+x)%c_mod; std::cout<<res; return 0; } |