#168663 (D) No.127 門松もどき

• 問題: No.127 門松もどき
• ユーザー: te-sh
• 提出日時: 2017-04-26 15:39:31
• 言語: D (dmd 2.106.1)
• 結果: WA
• 実行時間: -
• コード長: 886 bytes
• コンパイル時間: 915 ms
• コンパイル使用メモリ: 87,816 KB
• 実行使用メモリ: 76,488 KB
• 最終ジャッジ日時: 2023-09-03 13:00:52
• 合計ジャッジ時間: 3,861 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	1 ms; 4,384 KB
testcase_04	WA	-
testcase_05	AC	1 ms; 4,380 KB
testcase_06	WA	-
testcase_07	AC	2 ms; 4,380 KB
testcase_08	WA	-
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,376 KB
testcase_11	AC	2 ms; 4,376 KB
testcase_12	AC	115 ms; 55,040 KB
testcase_13	AC	138 ms; 64,044 KB
testcase_14	AC	150 ms; 61,188 KB
testcase_15	AC	201 ms; 71,364 KB
testcase_16	AC	126 ms; 60,620 KB
testcase_17	AC	144 ms; 65,212 KB
testcase_18	AC	115 ms; 60,588 KB
testcase_19	AC	67 ms; 32,692 KB
testcase_20	AC	78 ms; 32,740 KB
testcase_21	AC	33 ms; 22,624 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-

ソースコード

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!size_t;
  auto ai = readln.split.to!(int[]);

  auto calc = new Calc(n, ai);
  auto r = max(calc.calcA(0, n-1), calc.calcB(n-1, 0));

  writeln(r);
}

class Calc
{
  size_t n;
  int[] ai;
  int[][] dpa, dpb;

  this(size_t n, int[] ai)
  {
    this.n = n;
    this.ai = ai;
    dpa = new int[][](n, n);
    dpb = new int[][](n, n);
  }

  int calcA(size_t i, size_t j)
  {
    if (i == j) return 1;
    if (dpa[i][j]) return dpa[i][j];

    auto r = calcA(i, j-1);
    if (ai[i] < ai[j])
      r = max(r, calcB(j, i+1) + 1);

    return dpa[i][j] = r;
  }

  int calcB(size_t i, size_t j)
  {
    if (i == j) return 1;
    if (dpb[i][j]) return dpb[i][j];

    auto r = calcB(i, j+1);
    if (ai[i] < ai[j])
      r = max(r, calcA(j, i-1) + 1);

    return dpb[i][j] = r;
  }
}