1
class Solution {
2
 public:
3
  int dp[50001][2][2];
4

5
  int playGame(vector<int> &stones, bool alice, bool bob, int i) {
6
    if (i >= stones.size()) return 0;
7

8
    int ans;
9
    int sum = 0;
10

11
    if (dp[i][alice][bob] != -1) return dp[i][alice][bob];
12

13
    if (alice) {
14
      ans = INT_MIN;
15
      for (int idx = i; idx < i + 3 && idx < stones.size(); idx++) {
16
        sum += stones[idx];
17
        ans = max(ans, sum + playGame(stones, false, true, idx + 1));
18
      }
19
    }
20

21
    if (bob) {
22
      ans = INT_MAX;
23
      for (int idx = i; idx < i + 3 && idx < stones.size(); idx++) {
24
        sum += stones[idx];
25
        ans = min(ans, playGame(stones, true, false, idx + 1));
26
      }
27
    }
28

29
    return dp[i][alice][bob] = ans;
30
  }
31

32
  string stoneGameIII(vector<int> &stoneValue) {
33
    memset(dp, -1, sizeof dp);
34
    int totalScore = 0;
35
    for (auto i : stoneValue) totalScore += i;
36
    int aliceScore = playGame(stoneValue, true, false, 0);
37
    if (totalScore - aliceScore > aliceScore)
38
      return "Bob";
39
    else if (totalScore - aliceScore < aliceScore)
40
      return "Alice";
41
    else
42
      return "Tie";
43
  }
44
};