結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー bal4u
提出日時 2019-07-09 18:45:44
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,362 bytes
コンパイル時間 1,040 ms
コンパイル使用メモリ 30,464 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 11:06:47
合計ジャッジ時間 1,838 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: note: in expansion of macro 'gc'
   14 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.684 Prefix Parenthesis
// 2019.7.9 bal4u

#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

typedef struct { int l, r, d; } T;
T t[100005], s[100005]; int tz, sz;
int N;
long long ans, ls, rs;

int cmpt(const void *a, const void *b) {
	return ((T *)a)->r - ((T *)b)->r;
}

int cmps(const void *a, const void *b) {
	int t = ((T *)b)->d - ((T *)a)->d;
	if (t) return t;
	return ((T *)b)->l - ((T *)a)->l;
}

void eva(T *t, int sz) {
	int i;
	for (i = 0; i < sz; i++) {
		if (t[i].r <= ls) ans += t[i].r, ls -= t[i].r;
		else ans += ls, ls = 0;
		ls += t[i].l;
	}
}
	
int main()
{
	int i, l, r;

	N = in();
	l = r = 0;
	for (i = 0; i < N; i++) {
		if (gc() == '(') l++;
		else {
			if (l) l--, ans += N-i;
			else r++;
		}
		if (l >= r && ls >= r) ans += r, ls += l-r;
		else if (l == 0) rs += r;
		else if (l-r >= 0) t[tz].l = l, t[tz++].r = r;
		else s[sz].l = l, s[sz].r = r, s[sz++].d = l-r;
	}
//	printf("ans=%lld, ls=%lld, rs=%lld, tz=%d, sz=%d\n",
//		ans << 1, ls, rs, tz, sz);
	
	if (tz) qsort(t, tz, sizeof(T), cmpt), eva(t, tz);
	qsort(s, sz, sizeof(T), cmps);
	eva(s, sz);
	ans += (ls <= rs)? ls: rs;
	printf("%lld\n", ans << 1);
	return 0;
}
0