結果

問題 No.2591 安上がりな括弧列
ユーザー laneguelanegue
提出日時 2023-12-19 03:11:46
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 662 bytes
コンパイル時間 1,620 ms
コンパイル使用メモリ 102,504 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-27 08:36:22
合計ジャッジ時間 1,681 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 19 ms
6,944 KB
testcase_12 AC 18 ms
6,940 KB
testcase_13 AC 19 ms
6,940 KB
testcase_14 AC 19 ms
6,944 KB
testcase_15 AC 19 ms
6,940 KB
testcase_16 AC 19 ms
6,940 KB
testcase_17 AC 7 ms
6,944 KB
testcase_18 AC 11 ms
6,940 KB
testcase_19 AC 9 ms
6,940 KB
testcase_20 AC 19 ms
6,940 KB
testcase_21 AC 19 ms
6,940 KB
testcase_22 AC 19 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const ulong MAX_COST = 10UL ^^ 13;

void main(){
  auto N = readln.chomp.to!ulong;
  auto S = readln.chomp;
  auto A = readln.chomp.split.to!(ulong[]);

  auto prev = new ulong[N + 1];
  prev[] = MAX_COST;
  prev[0] = 0;
  foreach(i, c; S){
    auto cost = new ulong[N + 1];
    cost[] = MAX_COST;
    for(auto j = 0; j < N + 1; j++){
      if(j > 0){
        cost[j] = prev[j - 1] + (c == '(' ? 0 : A[i]);
      }
      if(j < N){
        cost[j] = min(cost[j], prev[j + 1] + (c == ')' ? 0 : A[i]));
      }
    }
    //stderr.writeln(cost);
    prev = cost;
  }
  prev[0].writeln;
}
0