Leet Code Weekly Contest 260

class Solution {
public:

    int maximumDifference(vector<int>& nums) {
        int ans = -1, n = nums.size();
        
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (nums[i] < nums[j])
                {
                    ans = max(ans, nums[j] - nums[i]);
                }
            }
        }
        
        return ans;
    }
};

// TC: O(n), SC: O(n)

typedef long long ll;

class Solution
{
public:
    
    vector<vector<ll>> make_sum(vector<vector<int>> &grid)
    {
        vector<vector<ll>> ret;
        
        for (int i = 0; i < grid.size(); i++)
        {
            vector<ll> sum({ 0 });
            
            for (auto &x : grid[i])
            {
                sum.push_back(sum.back() + x);
            }
            
            ret.push_back(sum);
        }
        
        return ret;
    }
    
    long long gridGame(vector<vector<int>>& grid)
    {
        int n = grid[0].size();
        vector<vector<ll>> sum = make_sum(grid);
        
        ll ans = LONG_MAX;
        
        for (int i = 0; i < n; i++)
        {
            ans = min(ans, max(sum[1][i], sum[0][n] - sum[0][i + 1]));
        }
        
        return ans;
    }
};

class Solution {
public:
    
    vector<pair<int, int>> directions = vector<pair<int, int>>(
    {
        make_pair( 0, -1),
        make_pair( 0, +1),
        make_pair(-1,  0),
        make_pair(+1,  0)
    });
    
    inline char get_char(vector<vector<char>> &board, int x, int y)
    {
        int n = board.size(), m = board[0].size();
        
        if (x < 0 || x >= n)
        {
            return '#';
        }

        if (y < 0 || y >= m)
        {
            return '#';
        }
        
        return board[x][y];
    }
    
    bool placeWordInCrossword(vector<vector<char>>& board, string word)
    {
        int n = board.size(), m = board[0].size(), len = word.length();
        
        for (int x = 0; x < n; x++)
        {
            for (int y = 0; y < m; y++)
            {
                for (auto &dir : directions)
                {
                    int dx = dir.first, dy = dir.second;
                    
                    if (get_char(board, x - dx, y - dy) != '#')
                    {
                        continue;
                    }
                    
                    if (get_char(board, x + dx * len, y + dy * len) != '#')
                    {
                        continue;
                    }
                    
                    for (int i = 0; i < len; i++)
                    {
                        int nx = x + dx * i;
                        int ny = y + dy * i;

                        char c = get_char(board, nx, ny);
                        
                        if (c != word[i] && c != ' ')
                        {
                            break;
                        }
                        
                        if (i == len - 1)
                        {
                            return true;
                        }
                    }
                }
            }
        }
        
        return false;
    }
};

class Solution {
public:
    
    int f(string s)
    {
        if (s.length() == 1)
        {
            return s[0] - '0';
        }
        
        // any + ?
        for (int i = 1; i < s.length(); i += 2)
        {
            if (s[i] == '+')
            {
                int a = f(s.substr(0, i));
                int b = f(s.substr(i + 1, s.length() - i - 1));
                
                return a + b;
            }
        }
        
        // all *
        int ret = 1;
        
        for (int i = 0; i < s.length(); i += 2)
        {
            ret = ret * (s[i] - '0');
        }
        
        return ret;
    }
    
    unordered_set<int> g_cache[32][32];
    
    unordered_set<int> &g(string &s, int left, int right)
    {
        if (g_cache[left][right].empty())
        {
            if (left == right)
            {
                g_cache[left][right] = unordered_set<int>({ s[left] - '0' });
            }
            else
            {
                unordered_set<int> ret;

                for (int i = left + 1; i < right; i += 2)
                {
                    for (auto &x : g(s, left, i - 1))
                    {
                        for (auto &y : g(s, i + 1, right))
                        {
                            int z = (s[i] == '+') ? (x + y) : (x * y);
                            
                            if (z <= 1000)
                            {
                                ret.insert(z);
                            }
                        }
                    }
                }
                
                g_cache[left][right] = ret;
            }
            
            /*
            cout << "g(" << key << "|" << s.substr(left, right - left + 1) << ") =";
            
            for (auto x : g_cache[left][right])
            {
                cout << " " << x;
            }
            
            cout << endl;
            */
        }
        
        return g_cache[left][right];
    }
    
    int scoreOfStudents(string s, vector<int>& answers)
    {
        int x = f(s);
        unordered_set<int> other = g(s, 0, s.length() - 1);
        
        int ans = 0;
        
        for (auto answer : answers)
        {
            if (answer == x)
            {
                ans += 5;
            }
            else if (other.find(answer) != other.end())
            {
                ans += 2;
            }
        }
        
        return ans;
    }
};