JAGContest2016DomesticD.java

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {

    private static final double EPS = 1e-10;
    private static int[][][][][][] memo = null;   //a1,a2,b1,b2(0-n),flag,pass 値は自分の点数-相手の点数の差
    private static final int ATURN = 0;
    private static final int BTURN = 1;
    //変数名のあとにかっこを付けると
    //java的には変

    private static final int NOT_CALCULATED = Integer.MAX_VALUE;

    private static int[] a;
    private static int[] b;
    private static int n;
    private static int m;

    public static void main(String args[]) {
        FastScanner sc = new FastScanner();
        n = sc.nextInt();
        m = sc.nextInt();

        memo = new int[2][3][n + 1][n + 1][m + 1][m + 1];//小→大

        init(n, m);

        a = new int[n];
        b = new int[m];

        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < m; i++) b[i] = sc.nextInt();

        System.out.println(minimax(0, 0, 0, 0, 0, 1, 0, 0));

    }

    //stackA,Bを計算しておくと得点計算のときにO(n)かけなくて済む
    //結局メモ化再帰．得点の表し方がぽいんと
    public static int minimax(int a1, int a2, int b1, int b2, int flag, int pass, int stackA, int stackB) {
        if (pass == 3) return 0;

        if (memo[flag][pass][a1][a2][b1][b2] != NOT_CALCULATED)
            return memo[flag][pass][a1][a2][b1][b2];

        if (flag == ATURN) {        //A
            int max = minimax(a2, a2, b2, b2, BTURN, pass + 1, 0, 0) + stackA - stackB;//pass<2なのでパスもしてみる

            if (a2 < n) {//おけるならおいてみる
                if (a[a2] == -1) {
                    max = Math.max(max,
                            minimax(a1, a2 + 1, b2, b2, BTURN, 0, stackA, 0));
                } else {
                    max = Math.max(max,
                            minimax(a1, a2 + 1, b1, b2, BTURN, 0, stackA + a[a2], stackB));
                }
            }

            memo[flag][pass][a1][a2][b1][b2] = max;

            return max;
        } else {                    //B
            int min = minimax(a2, a2, b2, b2, ATURN, pass + 1, 0, 0) + stackA - stackB;
            if (b2 < m) {//おけるならおいてみる
                if (b[b2] == -1) {
                    min = Math.min(min,
                            minimax(a2, a2, b1, b2 + 1, ATURN, 0, 0, stackB));
                } else {
                    min = Math.min(min,
                            minimax(a1, a2, b1, b2 + 1, ATURN, 0, stackA, stackB + b[b2]));
                }
            }
            memo[flag][pass][a1][a2][b1][b2] = min;

            return min;
        }


    }


    public static void init(int n, int m) {
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k <= n; k++)
                    for (int l = 0; l <= n; l++)
                        for (int o = 0; o <= m; o++)
                            for (int p = 0; p <= m; p++)
                                memo[i][j][k][l][o][p] = NOT_CALCULATED;
    }

}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) return buffer[ptr++];
        else return -1;
    }

    private boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    public boolean hasNext() {
        skipUnprintable();
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        if (!hasNext()) throw new NoSuchElementException();
        int n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
}