← Real problems

ioi96p1

mediuminterval-dpgamesStatement on DMOJ

CP Lang

12 lines0.3 spec
// ioi96p1 A Game: players take a number from either end; both play best. The mover's best total
// on a range is its sum minus the opponent's best on what is left.
let n = read<1..=100>()
domain I = [n]
let a = read<[I]0..=200>()
@memo(array)
fn best(r: I.ranges) -> Int:
    if r.first! == r.last!:
        return a[r.first!]
    a[r].sum() - min(best(r.drop(1)), best(r.drop_last(1)))
let first = best(I.range)
print(first, a.sum() - first)

Accepted C++

57 lines · 0.06 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

void solve() {
    int n;
    cin >> n;
    int arr[n];
    for (auto& a : arr) {
        cin >> a;
    }
    int dp[n][n];
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = arr[i];
        int csum = arr[i];
        for (int j = i + 1; j < n; j++) {
            csum += arr[j];
            dp[i][j] = csum - min(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    int csum = accumulate(arr, arr + n, 0);
    cout << dp[0][n - 1] << " " << csum - dp[0][n - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}