Codeforces Round #360 (Div. 1) - C. The Values You Can Make

Problem Statement:
http://codeforces.com/contest/687/problem/C

Summary:
n, k <= 500, with n integers c[i] <= 500, output all x such that there exists a subset S of c with sum k, and S has a subset with sum x.



Solution:
The dynamic programming used in this problem is a little bit different. Let dp[i][j][k] equals to 1 if in prefix c[0..i] there exists two disjoint subsets with sum j and k respectively. Then we have dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-c[i]][k], dp[i-1][j][k-c[i]]).

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, k;
int c[510];
bool dp[510][510][510];
int main(){
  scanf("%d%d",&n,&k);
  for(int i=0;i<n;++i){scanf("%d",&c[i]);}
  dp[0][0][0] = 1;
  dp[0][c[0]][0] = 1;
  dp[0][0][c[0]] = 1;
  for(int i=1;i<n;++i){
    dp[i][0][0] = 1;
    for(int s=0;s<=k;++s){
      for(int t=0;t<=k;++t){
        if (s-c[i]>=0) dp[i][s][t] = max(dp[i][s][t], dp[i-1][s-c[i]][t]);
        if (t-c[i]>=0) dp[i][s][t] = max(dp[i][s][t], dp[i-1][s][t-c[i]]);
        dp[i][s][t] = max(dp[i][s][t], dp[i-1][s][t]);
      }
    }
  }
  vector<int> ans;
  for (int s=0;s<=k;++s){
    if (dp[n-1][s][k-s]) ans.push_back(s);
  }
  printf("%d\n", (int)ans.size());
  for(int i : ans) {
    printf("%d ", i);
  }
  printf("\n");
  return 0;
}