v 0. Pasted by slipstak2 as cpp at 2010-11-23 22:54:07 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 6.
  2. // 6B. Суммы [sums]
  3. // ibelyaev: 20Nov2010
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. const int max_size = 50000 + 5;
  12. int n;
  13. vector<int> mas;
  14. void input()
  15. {
  16.     cin>>n;
  17.     mas.resize(n);
  18.     for (int i=0;i<n;i++)
  19.         scanf("%d", &mas[i]);
  20. }
  21. void solve()
  22. {
  23.     vector<int> met(max_size);
  24.     met[0] = 1;
  25.     int maxValue = 0;
  26.     for (int j = 0; j<mas.size();j++)
  27.     {
  28.         int newMaxValue = maxValue;
  29.         for (int i = maxValue;i>=0;i--)
  30.         {
  31.             if (met[i])
  32.             {
  33.                 met[i + mas[j]] = 1;
  34.                 newMaxValue = max(i + mas[j], newMaxValue);
  35.             }
  36.         }
  37.         maxValue = newMaxValue;
  38.     }
  39.  
  40.     int difAmount = 0;
  41.     for (int i=0;i<met.size();i++)
  42.         if (met[i])
  43.             difAmount++;
  44.     cout<<difAmount;
  45. }
  46. int main()
  47. {
  48.     freopen("input.txt","r",stdin);
  49.     freopen("output.txt","w",stdout);
  50.  
  51.     input();
  52.     solve();
  53.     return 0;
  54. }


Editing is locked.