結果
問題 |
No.2591 安上がりな括弧列
|
ユーザー |
![]() |
提出日時 | 2025-07-03 00:17:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 902 bytes |
コンパイル時間 | 3,534 ms |
コンパイル使用メモリ | 280,812 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2025-07-03 00:17:48 |
合計ジャッジ時間 | 5,164 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "settings/debug.cpp" #else #define Debug(...) void(0) #endif #define rep(i, n) for (int i = 0; i < (n); ++i) using ll = long long; using ull = unsigned long long; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; string s; cin >> n >> s; const int m = 2 * n; vector<ll> a(m); rep(i, m) cin >> a[i]; constexpr ll INF = 1e18; vector dp(m + 1, vector<ll>(n + 1, INF)); dp[0][0] = 0; rep(i, m) { char c = s[i]; int dif = (c == '(' ? 1 : -1); rep(j, n + 1) { if (dp[i][j] == INF) continue; // そのまま if (0 <= j + dif && j + dif <= n) dp[i + 1][j + dif] = min(dp[i + 1][j + dif], dp[i][j]); // かえる if (0 <= j - dif && j - dif <= n) dp[i + 1][j - dif] = min(dp[i + 1][j - dif], dp[i][j] + a[i]); } } cout << dp[m][0] << '\n'; return 0; }