## Tuesday, July 19, 2016

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