【題解】TIOJ 1508 . 加減問題

#include <iostream>
#include <bitset>
using namespace std;

int m, n, a[105], tar;
bitset <5005> dp;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    while (m--){
        tar = 0;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            tar += a[i];
        }
        if (tar % 2 != 0){
            cout << "No\n";
            continue;
        }
        tar /= 2;
        dp.reset();
        dp[0] = 1;
        for (int i = 1; i <= n; i++){
            for (int j = tar-a[i]; j >= 0; j--){
                if (dp[j]) dp[j+a[i]] = 1;
            }
        }
        if (dp[tar]) cout << "Yes\n";
        else cout << "No\n";
    }       
}