結果

問題 No.2591 安上がりな括弧列
コンテスト
ユーザー tnakao0123
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- 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;
}
0