結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー 梧桐
提出日時 2025-10-24 00:40:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 976 bytes
コンパイル時間 867 ms
コンパイル使用メモリ 74,680 KB
実行使用メモリ 7,724 KB
最終ジャッジ日時 2025-10-24 00:40:42
合計ジャッジ時間 2,503 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:16:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, l, r, ans;
string s;

struct Node {
    int L, R;
};
vector<Node> nodes;

int main() {
    scanf("%d", &n);
    cin >> s;

    for (int i = 0, match = 0; i < s.size(); ++i) {
        if (s[i] == '(') {
            ++l;
        } else {
            if (l > 0) {
                ++match;
                --l;
            } else {
                ++r;
            }
        }
        ans += match * 2;
        nodes.push_back({ l, r });
    }

    sort(nodes.begin(), nodes.end(), [](Node n1, Node n2) {
        bool n1_type = n1.R <= n1.L, n2_type = n2.R <= n2.L;
        if (n1_type != n2_type) return n1_type;
        if (n1.R <= n1.L) return n1.R < n2.R;
        return n1.L > n2.L;
    });

    l = 0LL;
    for (auto node : nodes) {
        int match = min(l, node.R);
        l -= match;
        l += node.L;
        ans += match * 2;
    }
    printf("%d\n", ans);

    return 0;
}
0