chiakeo.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 205;

int a[N], dp[N][N * 205], dd[N];

signed main() {
  int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum += a[i];
  }

  dp[0][0] = 1;
  for (int i = 1; i <= n; i++)
  for (int j = 0; j <= 40000; j++) {
    if (dp[i - 1][j] == 1) dp[i][j] = 1;
    if (j >= a[i] && dp[i - 1][j - a[i]] == 1) dp[i][j] = 1;
  }

  // in bang
  /*cout << "    ";
  for (int j = 0; j <= 20; j++) {
    cout << setw(2) << j << ' ';
  }
  cout << '\n';
  for (int j = 0; j <= 70; j++) {
    cout << '-';
  }
  cout << '\n';
  for (int i = 0; i <= n; i++) {
    cout << i << " | ";
    for (int j = 0; j <= 20; j++) {
      cout << setw(2) << dp[i][j] << ' ';
    }
    cout << '\n';
  }*/

  int i = n, j = sum / 2;
  while (dp[n][j] == 0) j--;

  cout << sum - j * 2 << '\n';

  // cout << "i = " << n << '\n';
  // cout << "j = " << j << '\n';

  while (i != 0 && j != 0) {
    // cout << i << ' ' << j << '\n';
    if (dp[i - 1][j] == 1) {
      i--;
    }
    else if (dp[i - 1][j - a[i]] == 1) {
      // cout << "dd = " << i << '\n';
      dd[i] = 1;
      j -= a[i];
      i--;
    }
  }

  for (int i = 1; i <= n; i++) {
    if (dd[i] == 0) cout << a[i] << ' ';
  }
  cout << '\n';

  for (int i = 1; i <= n; i++) {
    if (dd[i] == 1) cout << a[i] << ' ';
  }
  cout << '\n';
}