Top

(ΦωΦ)<これの答えですよー。目次はここ

---
問1-1
#include <iostream>
#include <algorithm>
using namespace std;

int n;
vector<int> w;
vector<vector<int>> dp;
int half;

// i番目を左に置こうか右に置こうか迷っている状態。
// これまでの左の重さはweight。
bool rec(int i, int weight) {
  if(dp[i][weight] != -1) { return dp[i][weight]; }
  if(i == n) { return weight==half; }
  return 
    dp[i][weight] = rec(i+1, weight+w[i]) ||
                    rec(i+1, weight);
}

int main(void) {
  scanf("%d", &n);
  w.assign(n, 0);
  int summa = 0;
  for(int i=0; i<n; i++) {
    scanf("%d", &w[i]);
    summa += w[i];
  }
  if(summa & 1) {
    puts("impossible");
    return 0;
  }
  dp.assign(n+1, vector<int>(summa+1, -1));
  half = summa / 2;
  puts(rec(0, 0) ? "possible" : "impossible");
  return 0;
}
    

(ΦωΦ)<おしまい