結果
問題 | No.2591 安上がりな括弧列 |
ユーザー |
![]() |
提出日時 | 2023-12-22 11:06:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,045 bytes |
コンパイル時間 | 508 ms |
コンパイル使用メモリ | 55,084 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-27 11:22:46 |
合計ジャッジ時間 | 1,315 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
/* -*- coding: utf-8 -*- * * 2591.cc: No.2591 安上がりな括弧列 - yukicoder */ #include<cstdio> #include<set> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_N = 1000; const int MAX_N2 = MAX_N * 2; /* typedef */ typedef long long ll; typedef pair<int,int> pii; typedef set<pii> spii; /* global variables */ char s[MAX_N2 + 4]; int as[MAX_N2]; /* subroutines */ ll check(int n2, char ob, char cb) { spii ps; ll sum = 0; for (int i = 0, d = 0; i < n2; i++) { if (s[i] == ob) { d++; } else { ps.insert(pii(as[i], i)); d--; if (d < 0) { sum += ps.begin()->first; s[ps.begin()->second] = ob; d += 2; ps.erase(ps.begin()); } } } return sum; } /* main */ int main() { int n; scanf("%d%s", &n, s); int n2 = n * 2; for (int i = 0; i < n2; i++) scanf("%d", as + i); ll s0 = check(n2, '(', ')'); reverse(s, s + n2); reverse(as, as + n2); ll s1 = check(n2, ')', '('); printf("%lld\n", s0 + s1); return 0; }