smarter solution of https://judge.npca.jp/problems/view/212

K_partial_sum_2.cpp

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

const int MAX_N = 605;
const int MAX_M = 180305;
const int INF = 1000;

int X[MAX_N];
int dp0[MAX_M];
int dp1[MAX_M];
int dpr[MAX_M];
inline void update(int& a, int b) { a = min(a,b);}

int main(){
  int N, K;
  // input
  cin >> N >> K;
  for (int i = 0; i < N; ++i) cin >> X[i];
  int m = accumulate(X, X+N, 0);
  // initialize
  for(int s = 0; s <= m; ++s) dp0[s] = dp1[s] = INF, dpr[s] = K;
  dp0[accumulate(X, X+K, 0)] = 0;
  // DP
  for (int j = K; j < N; ++j) {
    for (int s = 0; s <= m; ++s) update(dpr[s], dp1[s]);
    for (int s = 0; s <= m; ++s) update(dp1[s+X[j]], dp0[s]);
    for (int s = 0; s <= m; ++s) {
      if (dp1[s] != INF) {
        for (int i = dp1[s]; i < dpr[s]; ++i) {
          update(dp0[s-X[i]], i+1);
        }
      }
    }
  }
  // output
  string ans;
  for (int s = 0; s <= m; ++s) {
    ans += (dp0[s] == INF) ? '0' : '1';
  }
  cout << ans << endl;
  return 0;
}

解説記事 http://snuke.hatenablog.com/entry/2015/04/21/155048