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; } };