IOI '96 P1 - A Game

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    vector<vector<int>> score[2];
    score[0] = score[1] = vector<vector<int>>(n, vector<int>(n));
    for (int i = 0; i < n; ++i) score[0][i][i] = a[i];
    for (int sz = 2; sz <= n; ++sz) {
        for (int left = 0; left+sz <= n; ++left) {
            int right = left+sz-1;
            int opt1 = a[left] + score[1][left+1][right];
            int opt2 = a[right] + score[1][left][right-1];
            if (opt1 > opt2) {
                score[0][left][right] = opt1;
                score[1][left][right] = score[0][left+1][right];
            } else {
                score[0][left][right] = opt2;
                score[1][left][right] = score[0][left][right-1];
            }
        }
    }
    cout << score[0][0][n-1] << ' ' << score[1][0][n-1] << endl;
    return 0;
}