Untitled
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; }