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

K_partial_sum.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_N][MAX_M];
int dp1[MAX_N][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 j = K; j <= N; ++j) for(int s = 0; s <= m; ++s) {
    dp0[j][s] = dp1[j][s] = INF;
  }
  dp0[K][accumulate(X, X+K, 0)] = 0;
  // DP
  for (int j = K; j <= N; ++j) {
    for (int s = 0; s <= m; ++s) {
      if (dp1[j][s] != INF) {
        update(dp1[j+1][s], dp1[j][s]);
        int l = dp1[j][s], r = K;
        if (j > 0) update(r, dp1[j-1][s]);
        for (int i = l; i < r; ++i) {
          update(dp0[j][s-X[i]], i+1);
        }
      }
    }
    for (int s = 0; s <= m; ++s) {
      if (dp0[j][s] != INF) {
        update(dp0[j+1][s], dp0[j][s]);
        update(dp1[j+1][s+X[j]], dp0[j][s]);
      }
    }
  }
  // output
  string ans;
  for (int s = 0; s <= m; ++s) {
    ans += (dp0[N][s] == INF) ? '0' : '1';
  }
  cout << ans << endl;
  return 0;
}

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