Submission #620442

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }


    static int Calc_1(int turn, int ap, int[] a, int bp, int[] b, int[,] memo) {
        if (ap == a.Length && bp == b.Length) return 0;

        if (memo[ap, bp] > 0) return memo[ap, bp];

        int ret = 0;
        if (turn == 0) { // snuke
            if (ap < a.Length) {
                ret = Math.Max(ret, a[ap] + Calc_1(1, ap+1, a, bp, b, memo));
            }
            if (bp < b.Length) {
                ret = Math.Max(ret, b[bp] + Calc_1(1, ap, a, bp+1, b, memo));
            }
        }
        else { // smeke
            ret = int.MaxValue;
            if (ap < a.Length) {
                ret = Math.Min(ret, Calc_1(0, ap+1, a, bp, b, memo));
            }
            if (bp < b.Length) {
                ret = Math.Min(ret, Calc_1(0, ap, a, bp+1, b, memo));
            }
        }

        return memo[ap, bp] = ret;
    }

    static int Calc(int[] a, int[] b) {
        var memo = new int[a.Length+1, b.Length+1]; // [左の山, 右の山]
        return Calc_1(0, 0, a, 0, b, memo);
    }

    static void Main() {
        ReadLine();
        var a = ReadInts();
        var b = ReadInts();

        var ans = Calc(a, b);
        Console.WriteLine(ans);
    }
}

Submission Info

Judge Result