Typical DP Contest - A コンテスト

A: コンテスト - Typical DP Contest | AtCoder

class a_contest {
public:
    void solve(void) {
            int N;
            cin>>N;
            vector<int> p(N,0);
            REP(i, N)
                cin>>p[i];

            sort(RANGE(p));
            int M = 10100;
            vector<bool> dp(M, false);

            dp[0] = true;
            REP(i, N)
            {
                // 順方向だとたった今更新された dp の結果から再度更新
                // されてしまうので逆方向でやる
                for (int j = M; j >= 0; --j)
                    dp[p[i]+j] = (dp[p[i]+j] || dp[j]);
            }
            int cnt=0;
            REP(i, dp.size())
                if (dp[i])
                    ++cnt;
            cout<<cnt<<endl;
    }
};