Submission #61772653

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define in(a)                                                                  \
    for (auto &x : a)                                                          \
        cin >> x;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define out(a)                                                                 \
    for (auto x : a)                                                           \
        cout << x << " ";
#define pb push_back
#define int long long
typedef vector<int> vi;
typedef pair<int, int> pii;
// turn = 0: first
// turn = 1: second
// total: reduce it

int solve(int player, int total, vector<int> &moves)
{
    int win = 0;
    for (auto &x : moves) {
        if (total - x >= 0) {
            if (!solve(player ^ 1, total - x, moves)) {
                win = 1;
                break;
            }
        }
    }
    return win;
}
void solve()
{
    int n, total;
    cin >> n >> total;
    vi v(n);
    in(v);
    vector<vector<int>> dp(2, vector<int>(total + 1, 0));
    // dp[i][j] = {!dp[i^1][j-x]} for all x in v
    // that is there is one way that I can win
    // then mark as true

    for (int j = 0; j <= total; j++) {
        for (int i = 0; i < 2; i++) {
            for (auto x : v) {
                if (j - x >= 0) {
                    if (dp[i ^ 1][j - x] == 0) {
                        dp[i][j] = 1;
                        break;
                    }
                }
            }
        }
    }

    cout << (dp[0][total] ? "First" : "Second") << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Submission Info

Judge Result