結果
問題 | No.684 Prefix Parenthesis |
ユーザー |
|
提出日時 | 2019-03-08 04:24:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 756 bytes |
コンパイル時間 | 482 ms |
コンパイル使用メモリ | 58,952 KB |
最終ジャッジ日時 | 2025-01-06 22:01:29 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:21:9: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 21 | scanf ("%d%s", &n, S); | ~~~~~~^~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <vector> #include <algorithm> using int64 = long long; const int N = 1e5 + 10; struct node { int64 p, q; bool operator < (const node &t) const{ if (q >= 0 && t.q >= 0) return p > t.p; return q > t.q; } }; char S[N]; int n; int main() { scanf ("%d%s", &n, S); int64 b = 0, mn = 0; std::vector<node> V(n); for (int i = 0; i < n; i++) { if (S[i] == '(') b++; else { b--; if (mn > b) mn = b; } V[i] = {mn,b}; } std::sort(V.begin(), V.end()); int64 ab = 0, amn = 0; for (int i = 0; i < n; i++){ if (amn > ab + V[i].p) { amn = ab + V[i].p; } ab += V[i].q; } int64 len = (int64)n * (n + 1) / 2 - ab + 2 * amn; printf ("%lld\n", len); return 0; }