Paste will expire never.
- // Меньшиков. Тренировка 6.
- // 6B. Суммы [sums]
- // ibelyaev: 20Nov2010
- #include <iostream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- const int max_size = 50000 + 5;
- int n;
- vector<int> mas;
- void input()
- {
- cin>>n;
- mas.resize(n);
- for (int i=0;i<n;i++)
- scanf("%d", &mas[i]);
- }
- void solve()
- {
- vector<int> met(max_size);
- met[0] = 1;
- int maxValue = 0;
- for (int j = 0; j<mas.size();j++)
- {
- int newMaxValue = maxValue;
- for (int i = maxValue;i>=0;i--)
- {
- if (met[i])
- {
- met[i + mas[j]] = 1;
- newMaxValue = max(i + mas[j], newMaxValue);
- }
- }
- maxValue = newMaxValue;
- }
- int difAmount = 0;
- for (int i=0;i<met.size();i++)
- if (met[i])
- difAmount++;
- cout<<difAmount;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
Editing is locked.