提出 #710444

---

ソースコード 拡げる

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  Scanner sc;

  Main() {
    sc = new Scanner(System.in);
  }

  int ni() {
    return sc.nextInt();
  }

  public static void main(String[] args) {
    new Main().run();
  }

  int[][][][][][] memo;
  boolean[][][][][][] done;

  int dfs(int index, int limit, int jndex, int mimit, int turn, int pass) {
    if (pass == 3) {
      return 0;
    }
    if (done[turn][pass][index][limit][jndex][mimit]) {
      return memo[turn][pass][index][limit][jndex][mimit];
    }
    int add = sum[limit][index];
    int bdd = tum[mimit][jndex];

    if (turn == 0) {
      // player 1:max
      // 出す
      int U = -1 * (1 << 28);
      if (index < n) {
        int num = a[index];
        if (num == -1) {
          // 相手のカードを無効化
          mimit = jndex;
        }
        U = dfs(index + 1, limit, jndex, mimit, 1 - turn, 0);
      }
      // パス:limit to index
      int P = dfs(index, index, jndex, jndex, 1 - turn, pass + 1) + add - bdd;
      memo[turn][pass][index][limit][jndex][mimit] = Math.max(P, U);
    } else {
      // player 2:min
      // 出す
      int U = 1 << 28;
      if (jndex < m) {
        int num = b[jndex];
        if (num == -1) {
          // 相手のカードを無効化
          limit = index;
        }
        U = dfs(index, limit, jndex + 1, mimit, 1 - turn, 0);
      }
      // パス:limit to index
      int P = dfs(index, index, jndex, jndex, 1 - turn, pass + 1) + add - bdd;
      memo[turn][pass][index][limit][jndex][mimit] = Math.min(P, U);
    }

    done[turn][pass][index][limit][jndex][mimit] = true;
    return memo[turn][pass][index][limit][jndex][mimit];
  }

  int n, m;
  int N, M;
  int[] a, b;
  int[][] sum, tum;

  void run() {
    n = ni();
    m = ni();
    a = new int[n];
    b = new int[m];
    for (int i = 0; i < n; ++i) {
      a[i] = ni();
    }
    for (int i = 0; i < m; ++i) {
      b[i] = ni();
    }

    sum = new int[n + 1][n + 1];
    for (int i = 0; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j) {
        for (int k = i; k < j; ++k) {
          if (a[k] == -1) {
            continue;
          }
          sum[i][j] += a[k];

        }
      }
    }
    tum = new int[m + 1][m + 1];
    for (int i = 0; i <= m; ++i) {
      for (int j = i + 1; j <= m; ++j) {
        for (int k = i; k < j; ++k) {
          if (b[k] == -1) {
            continue;
          }
          tum[i][j] += b[k];
        }
      }
    }

    N = n + 1;
    M = m + 1;

    memo = new int[2][3][N][N][M][M];
    done = new boolean[2][3][N][N][M][M];
    for (int i = 0; i < N * N; ++i) {
      for (int j = 0; j < M * M; ++j) {
        for (int k = 0; k < 3; ++k) {
          memo[0][k][i / N][i % N][j / M][j % M] = -(1 << 28);
          memo[1][k][i / N][i % N][j / M][j % M] = 1 << 28;
        }
      }
    }

    System.out.println(dfs(0, 0, 0, 0, 0, 1));
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }
}

提出情報

ジャッジ結果