Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.1 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define sws std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define endl "\n"
#define pb push_back
#define all(x) x.begin(), x.end()

const int MOD = 1e9+7;
const int MAX = 5005;
const int INF = 0x3f3f3f3f3f3f3f3f;

int tab[MAX][MAX];

int solve(int l, int r, bool turno, vector<int> &v){
	if(l > r) return 0;
	if(tab[l][r] != -1) return tab[l][r];
	int ans = -INF;
	if(turno){
		ans = max(ans, v[l] + solve(l+1, r, !turno, v));
		ans = max(ans, v[r] + solve(l, r-1, !turno, v));
	} else {
		if(v[l] > v[r]) ans = - v[l] + solve(l+1, r, !turno, v);
		else ans = - v[r] + solve(l, r-1, !turno, v);
	}
	return tab[l][r] = ans;
}

int32_t main(){
    sws;

	int n; cin >> n;
	vector<int> v(2*n);
	for(int i=0; i<2*n; i++){
		cin >> v[i];
	}
	memset(tab, -1, sizeof(tab));
	solve(0, 2*n - 1, true, v);

	// odeio recuperar caminho :)
	for(int i=0; i<2*n; i++){
		for(int j=0; j<2*n; j++){
			cout << tab[i][j] << ' ';
		}
		cout << endl;
	}


    return 0;
}