fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7. template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. #define inf 1e9
  10. #define MOD 1000000007
  11.  
  12. void solve() {
  13.     ll n ; cin >> n ;
  14.     vector < int > a(n) ;
  15.     vector < int > dp(1e5+7 , 0   ) ;
  16.     for (int i = 0 ; i < n ; i++) {
  17.          cin >> a[i] ;
  18.  
  19.     }
  20.     ll ans = 0  ;
  21.     for (int  i = 0 ; i< n ; i++) {
  22.         for (int x  = 1e5 ;  x >= 1  ; x -- ) {
  23.             if (x - a[i] >= 1  && dp[x-a[i]] && ! dp[x] ) {
  24.                 dp[x] = 1 ;
  25.                 ans++ ;
  26.             }
  27.  
  28.         }
  29.         if (!dp[a[i]] ) {
  30.             dp[a[i]] = 1 ;
  31.             ans++ ;
  32.         }
  33.     }
  34.     cout << ans << endl ;
  35.     for (int  i = 1 ; i <=1e5 ; i ++ ) {
  36.         if (dp[i]) cout << i  << " "   ;
  37.  
  38.     }
  39.     cout << endl ;
  40. }
  41.  
  42. int main() {
  43.     ios::sync_with_stdio(false);
  44.     cin.tie(0);
  45. #ifndef ONLINE_JUDGE
  46.     freopen("input.txt", "r", stdin);
  47.     freopen("output.txt", "w", stdout);
  48. #endif
  49.     ll t = 1;
  50.  
  51.     //cin >> t;
  52.     while (t--) {
  53.         solve();
  54.     }
  55.     return 0;
  56. }
Success #stdin #stdout 0.05s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/qkNkmx
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!