SRM228-D1-500 BagsOfGold

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;

class BagsOfGold {
    public:
    int a[50],mem[50][50];

    int solve(int s, int e) {
        if(s > e) {
            return 0;
        }
        if(s == e) {
            return a[s];
        }
        if(mem[s][e] != -1) {
            return mem[s][e];
        }
        int &ret = mem[s][e];
        ret = max(a[s]-solve(s+1,e),a[e]-solve(s,e-1));
        return ret;
    }

    int netGain(vector <int> bags) {
        for(int i = 0; i < bags.size(); i++) {
            a[i] = bags[i];
            for(int j = i; j < bags.size(); j++) {
                mem[i][j] = -1;
            }
        }
        return solve(0,bags.size()-1);
    }
};

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    return 0;
}