結果

問題 No.2591 安上がりな括弧列
ユーザー lanegue
提出日時 2023-12-19 03:11:46
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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