QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500769#5246. Nawiasowe podziały [B]Sktn00891 49ms13684kbC++142.7kb2024-08-01 19:51:442024-08-01 19:51:45

Judging History

你现在查看的是最新测评结果

  • [2024-08-01 19:51:45]
  • 评测
  • 测评结果:1
  • 用时:49ms
  • 内存:13684kb
  • [2024-08-01 19:51:44]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pir pair <ll, ll>
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const ll maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e14;
ll n, k, stk[maxn], top, cnt, ggc, lpos[maxn], rpos[maxn];
char s[maxn];
vector <ll> son[maxn];
pir dp[maxn], f[maxn];
ll gain, q[maxn], l, r, sum[maxn], usum[maxn];
ll getx(ll i) {return i;}
ll gety(ll i) {return i * (i + 2) + 2 * (dp[i].fi - sum[i]);}
ll dx(ll i, ll j) {return getx(j) - getx(i);}
ll dy(ll i, ll j) {return gety(j) - gety(i);}
void dfs(ll u) {
	if(son[u].empty()) {
		usum[u] = 0;
		if(lpos[u] > 0 && rpos[u] <= n) f[u] = mkp(gain, 1);
		else f[u] = mkp(inf, 0);
		return;
	}
//	printf("dfs %lld\n", u);
	for(ll v: son[u]) dfs(v);
	l = 1, r = 0; ll cc = 0;
	for(ll i = 0; i < son[u].size(); i++) {
		ll v = son[u][i]; sum[i] = usum[v];
		if(i) sum[i] += sum[i - 1];
		dp[i].fi = f[v].fi + (cc + 1) * cc / 2 + (i? sum[i - 1] : 0);
		dp[i].se = f[v].se;
		cc += (lpos[v] > 0 && rpos[v] <= n);
		ll tmp = 1e18;
		while(l < r && dy(q[l], q[l + 1]) <= (__int128) dx(q[l], q[l + 1]) * 2 * i) {
			if(dy(q[l], q[l + 1]) == (__int128) dx(q[l], q[l + 1]) * 2 * i)
				tmp = min(tmp, dp[q[l]].se);
			++l;
		} tmp = min(tmp, dp[q[l]].se);
		if(i) { pir w; ll j = q[l];
			w.fi = dp[j].fi + sum[i - 1] - sum[j] + f[v].fi + 
			       (i - j) * (i - j - 1) / 2;
			w.se = tmp + f[v].se;
			dp[i] = min(dp[i], w);
		}
		while(l < r && (__int128) dy(q[r - 1], q[r]) * dx(q[r], i)
		> (__int128) dy(q[r], i) * dx(q[r - 1], q[r])) --r;
		q[++r] = i;
	} usum[u] = sum[son[u].size() - 1], f[u].fi = 1e18;
	for(ll i = 0; i < son[u].size(); i++) {
		pir w; ll gg = son[u].size() - i - 1;
		if(rpos[son[u][son[u].size() - 1]] > n) --gg;
		w.fi = dp[i].fi + usum[u] - sum[i]
		       + gg * (gg + 1) / 2;
		w.se = dp[i].se;
		f[u] = min(f[u], w);
	}
	usum[u] += cc * (cc + 1) / 2;
}
int main() {
//	freopen("p.in", "r", stdin);
//	freopen("p.out", "w", stdout);
	scanf("%lld%lld%s", &n, &k, s + 1);
	for(ll i = 1; i <= n; i++)
		if(s[i] == '(') ++cnt;
		else --cnt, ggc = min(ggc, cnt);
	cnt = 0, stk[top = 1] = cnt = 1;
	while(ggc++) {
		son[stk[top]].pb(++cnt);
		lpos[stk[++top] = cnt] = 0;
	}
	for(ll i = 1; i <= n; i++)
		if(s[i] == '(') {
			son[stk[top]].pb(++cnt);
			lpos[stk[++top] = cnt] = i;
		}
		else rpos[stk[top--]] = i;
	while(top > 1) rpos[stk[top--]] = n + 1;
	ll lo = 0, hi = 1e10, ans;
	while(lo <= hi) {
		gain = lo + hi >> 1, dfs(1);
		pir tmp = min(f[1], mkp(usum[1], 0ll));
		if(tmp.se < k) {
			ans = tmp.fi - gain * (k - 1);
			hi = gain - 1;
		} else lo = gain + 1;
	}
	printf("%lld", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 0ms
memory: 12084kb

input:

1 1
(

output:

0

result:

ok single line: '0'

Test #2:

score: 1
Accepted
time: 2ms
memory: 10112kb

input:

1 1
)

output:

0

result:

ok single line: '0'

Test #3:

score: 1
Accepted
time: 2ms
memory: 11896kb

input:

2 1
()

output:

1

result:

ok single line: '1'

Test #4:

score: 1
Accepted
time: 0ms
memory: 12152kb

input:

2 1
)(

output:

0

result:

ok single line: '0'

Test #5:

score: 1
Accepted
time: 1ms
memory: 12064kb

input:

2 2
()

output:

0

result:

ok single line: '0'

Test #6:

score: 1
Accepted
time: 1ms
memory: 12080kb

input:

2 2
)(

output:

0

result:

ok single line: '0'

Test #7:

score: 1
Accepted
time: 1ms
memory: 12092kb

input:

10 4
()))(()(()

output:

0

result:

ok single line: '0'

Test #8:

score: 1
Accepted
time: 0ms
memory: 12068kb

input:

15 4
())))()(()()(((

output:

1

result:

ok single line: '1'

Test #9:

score: 1
Accepted
time: 0ms
memory: 12152kb

input:

18 18
(()()()))(())(((((

output:

0

result:

ok single line: '0'

Test #10:

score: 1
Accepted
time: 1ms
memory: 12160kb

input:

18 3
(())(()()()())()()

output:

7

result:

ok single line: '7'

Test #11:

score: 1
Accepted
time: 1ms
memory: 12156kb

input:

17 5
()()(())()(()()()

output:

3

result:

ok single line: '3'

Test #12:

score: 1
Accepted
time: 0ms
memory: 9984kb

input:

17 4
()(()()())(()()()

output:

4

result:

ok single line: '4'

Test #13:

score: 1
Accepted
time: 0ms
memory: 12084kb

input:

18 4
()(()())(())()()()

output:

4

result:

ok single line: '4'

Test #14:

score: 1
Accepted
time: 2ms
memory: 10044kb

input:

18 4
(())()(())()()(())

output:

4

result:

ok single line: '4'

Test #15:

score: 1
Accepted
time: 1ms
memory: 9960kb

input:

18 4
(()())(()())()(())

output:

3

result:

ok single line: '3'

Subtask #2:

score: 0
Wrong Answer

Test #16:

score: 1
Accepted
time: 0ms
memory: 12160kb

input:

300 25
((()()()(()())(((())())()))()((()(())))((()()))((()()))()()(((())())))((((())(()()()())(((()))(()())()(())())()()()()())(()((()()()))))(())()((()))((()))(()(()())))((()(())(((()))))((()()()()()())())(((()))()()()(())())(())()(((()))()((()()())))((())())(((()())())((()))(()()()()(())(()())((()...

output:

90

result:

ok single line: '90'

Test #17:

score: 1
Accepted
time: 0ms
memory: 12084kb

input:

300 1
((((()))((((())))(())((()()(()())()())()()())()()())((()(()(())))((()))))()()(((())())))((((()((()))(())())))()(((())(())(())()()))((()()()())((())()())((()()(()(())))(()()))())()(((()()(()))))((()())()((()()(()()()())()(())()(()())()))((()()(())()())()()())((()((())())()))))(((())()(())(((())...

output:

332

result:

ok single line: '332'

Test #18:

score: 1
Accepted
time: 1ms
memory: 12008kb

input:

300 4
((((((()(())()())))(((()()(())())))()())((((((()()))))()((())(()((())))()()())(()(()()(()())())()))(()(()())(()())())(((())))(()())()(()((()()())(()()((())))((()((())())))(((()())()))(()))()((()))()()()()()()()(()(()(())()))(()(()()()()())()(()))))()(((()())))((()(())()))((()()(()()((()()(()))...

output:

250

result:

ok single line: '250'

Test #19:

score: 1
Accepted
time: 2ms
memory: 10124kb

input:

300 1
(((()((()(()()()())()))((()))((()()(()(())())(()())()())()(()))((()()()))()((()(()())()()(()()))(()(()()()))()())()(()(())(())(())()(())(()())((())()()(())())(()((()))(()))(()(((()())))(()))((()()))()()(((()))))(()()(((()()))))(()()))()(()((((()()))(((()))))()())()(()((()())())(())(((()())(())...

output:

400

result:

ok single line: '400'

Test #20:

score: 1
Accepted
time: 1ms
memory: 9984kb

input:

300 2
()((())()(())()()()()(()))(()(())(()))(()())(()()()()()()(()()())())(()())()(()()(()()())()((())()))(()()())(()())((()()(()))(()())()()())(()()()()())((()()))(()(())(()()))((()())(()())()(()(()()()())())()())(()())(()()()()()(())(()()))((()()()))(())(()(()())(()()))()(((()))()()()()(()())())((...

output:

453

result:

ok single line: '453'

Test #21:

score: 1
Accepted
time: 2ms
memory: 10044kb

input:

300 169
(((()))()()())(()(()(())))(()(()()())()(())()(())(()()()))(()(()))(()()(()())(()))(()()())()()(()(())(()()())(()))()((()))(())((())(())()((()))()()())(()()(()()))((()))((()()))(()()(()))(()())(())()(())(()()())()(()())(())((()())(()()))()(())(()(()))(()()(()()))()(()())(())(()(()))(((()))()(...

output:

0

result:

ok single line: '0'

Test #22:

score: 1
Accepted
time: 0ms
memory: 12020kb

input:

300 1
)((())(()()(()))(())))((()()()))))((((()))))()())()))((())))()))(())))()()))))())(())()())((((((()))(((()())())((())()(()(()()((()(())))())((()())())))()())))(((()(((()(((()))(()((()())))(((((((()(())((((()((()()())(((()))()((()()((((((()())))((()())))))))())()(())))()))()(()()()(((()(()))())(...

output:

202

result:

ok single line: '202'

Test #23:

score: 1
Accepted
time: 0ms
memory: 9932kb

input:

300 2
)(())((())))(()()(((())(((()((((()()))())(((((())))))((())())())))(((((()((((())(()())))))))))((()()))(()))((()())(())(()(((((((((()))()(())(((((()(((()())(()))))()))((()((())())))((((((((()(())((()))()()(())(()()()()()))()())())()(()(((()))((()()(((((())(()))(()(()(((()(()))(()(((())((()(((((...

output:

181

result:

ok single line: '181'

Test #24:

score: 1
Accepted
time: 2ms
memory: 12000kb

input:

300 7
()((()))())())((((()()(((())))))())()((()))()(())()())((()))))((((((()))((()()))())((()()()(()()((()((())))))))(()((()()(())()((())((((((()())(()))()))())))))(((()()())))()()(()))()))(()()(()()))()((())))((()(())(())(())()())())()))))(((())(()))))))()()(()()(())))))))))()()(()))(())()()(()))))...

output:

148

result:

ok single line: '148'

Test #25:

score: 1
Accepted
time: 2ms
memory: 12152kb

input:

290 15
))(())())(((()()()))((()())))(()))()()))())()())()((()))))())()))(()()(()))()())(())((()()())((())()))(()(())))))(())(()(((()))((()))()((())()(((())(((()))((((((()()()(((()(()((()))(())(())(((()()()())()())()((()())()()(()()))))())(())))))(()()(()()())))()))()))))))())(((())(()))))())()(((

output:

88

result:

ok single line: '88'

Test #26:

score: 1
Accepted
time: 0ms
memory: 12160kb

input:

300 30
(()((()()))(()))()(((())(()()))(((()(())()))()(()(()(((())))(((((((())()(()())()((((()((()(((((()()))()()))()))()(()()())))(())(()((((())(()(((()()))))))))))()(()())))))))())()))((()())()())())())))))((())()))()()(())())())())(()))()(()))(()(((((()))))((()((()))))()()))(()(()((((((()()(((((((...

output:

42

result:

ok single line: '42'

Test #27:

score: 1
Accepted
time: 0ms
memory: 12092kb

input:

300 300
((()())))))))))()()(()((())((()())))))(())))((()(((((()))())(((())))))((((())(()())()((((((())(()(())))())))())))()))((((()())((((((()())((())()(())(()()))(((()(())))))()())())()()(()))()()()))))(()())())()())(()((((())((((()()((()))()((((())(((((((())(()())((()()())(()())))(((()))))(()(())(...

output:

0

result:

ok single line: '0'

Test #28:

score: 1
Accepted
time: 0ms
memory: 12092kb

input:

300 1
(()((()))(()()((()(()()(()(()(()())()(()())()()(()(((()())))()())((()()((((())()(()(()()(((()(()))())()))((())))(())((((((())(((((())())((()())))((())(((()))(()(((((())((())))))))))))))((())((())(())))))(((((())))((()))((((()))()())))((((()))(()))()()))()(((((())))))((()))(()()())(()(()))()(((...

output:

261

result:

ok single line: '261'

Test #29:

score: 1
Accepted
time: 2ms
memory: 12160kb

input:

300 2
(((((((()))((((()(())))())))))))(((((((((((((((((((((())))))))))))))))))))))()))())))))(()())()()))(((())()())(())(()()(((())(()()()(()(()()((())((())))()()()((())))())(((()()))(())(((((())())(()())()()(())()(())(())()()(())((()()())())((())((())()))(()()(())(())())((()))()((())()()(())())((()...

output:

280

result:

ok single line: '280'

Test #30:

score: 0
Wrong Answer
time: 0ms
memory: 12100kb

input:

298 7
(((((((())((((((())(((((()((((((((())(((()((())())))))))())()))))())())(()))())))())(((())))))))))((()((()(((()(()()))))))))))())(())())())((()((((((()())(()))))))(())((((((((((((()))))))))))))(()())(())()()()(()()()((()))()())((())()(()))(()()(()))((()))(((())()())(())()()()())(()()())()(()()...

output:

122

result:

wrong answer 1st lines differ - expected: '123', found: '122'

Subtask #3:

score: 0
Wrong Answer

Test #33:

score: 1
Accepted
time: 3ms
memory: 12120kb

input:

4000 1
(((((())())()((())(())(()()())()())(()(())(()))()(()))(()((())()()()()(()())(()()()))()(())()()(()(()()())))(()))(()(((()))()())((())(()()(()()))))((()((()())())((())())((()()))(())(())(()(()()))(((())())())((())()()(()))(()()()(()(())(()))()())((()))((())()(())()())))(((()(()()()()())(())())...

output:

5599

result:

ok single line: '5599'

Test #34:

score: 1
Accepted
time: 3ms
memory: 12056kb

input:

4000 3
(((((((())))()()((((())(())()())()())(()(()())())))(()((())()((()()()((())()()))()))(())(()(()))()(()()()()((()(()))())()((()()()))(())(()()((())())))))(()(((((())))())((()()(((()()))())())())(())(()())(((()))())(()((()()()))(((()))())())())((())(())((())(())()(())()(((()))((())))))(((((())))...

output:

4568

result:

ok single line: '4568'

Test #35:

score: 1
Accepted
time: 3ms
memory: 12116kb

input:

4000 8
(((()))((()()(()())(()())((()))(((())))))(((())()(())()()()()((())())())((())()((())()))()(((())())()())(((()()()))(()()()(())(()))))(()()((()))((()())())((())(())()(())))(((((()()()())))(()()(()()())()()))()((())(()(()))((())()())((()()))()())(((())())()((()())(()()(())())()()((())))(())()((...

output:

4780

result:

ok single line: '4780'

Test #36:

score: 1
Accepted
time: 3ms
memory: 12136kb

input:

4000 21
(((((()())(())()))(()(())((((())())))()((()))()(()())()((())()())()()((((()))))))(((((()())()()()))((()))())((()))(()()(()))(()()((())))(())((()()())())(()()(())))(((())(()((())))()()(())(()((()()())(()))(()))))((()()((()()()())()())(()((()()()())())))(()()(((())()())()()((())(()))()(()))()(...

output:

3864

result:

ok single line: '3864'

Test #37:

score: 1
Accepted
time: 0ms
memory: 12140kb

input:

4000 55
((((()))((((()())))())(())((()()())((()))(()()(()((())()((())))()())(()))((()())(()())()()))))((((())))(()()(((())())())()((()))(()(()(()))(())())())((((()())(((()))())())((())())(()((()(())()(()())))()(()()(())))))(((((())()))((()())(())()()(())()()(()())())(()()(())((()()()))))))((()(())((...

output:

2909

result:

ok single line: '2909'

Test #38:

score: 1
Accepted
time: 3ms
memory: 12224kb

input:

4000 2
(((()())()(()())(())((()()))()())()((((())))())()()(()()(()())(())(()())()(())))(((())((()))(()((())))((()())((()())()())(()))((()))()(())(()())(())(())()(()()((())))()(())(())()()())()((((()))()()))((()()((()))())(())(())()()((()))()(()())(()))((())(((())()))())((()(()())(()()))(()(()))())((...

output:

5959

result:

ok single line: '5959'

Test #39:

score: 1
Accepted
time: 0ms
memory: 12120kb

input:

4000 5
(((((()())()))()(()((()())(()()())())((())((()()())()()))()(())(()()()(()))()((()))()()(((((()))))(()))()()()(()()))(((())(()(()))()()(()())(())()(()))())(()()())((()(()(()())()))(()(()()()()(())))))(((())((()())()()(())()()(())))((((()))(())())((())(())))((()))(()())((((()))))(((())))(()(())...

output:

4784

result:

ok single line: '4784'

Test #40:

score: 0
Wrong Answer
time: 3ms
memory: 12140kb

input:

4000 30
((((()()(()())(()(())((()(()))()))(()(()((()))))(())()((()())()((())())()((())()))())()((())())(((()))()()((())(()))(()())(((()))())(())))()((()(((())))((((()))()()()()()()(())())(())(())()(())))())(((())()()((((()))())())))(((()(()))))((()(()(()())()()()()(()))()))((()((())()())((()()())())...

output:

3347

result:

wrong answer 1st lines differ - expected: '3346', found: '3347'

Subtask #4:

score: 0
Wrong Answer

Test #54:

score: 1
Accepted
time: 0ms
memory: 12024kb

input:

4000 2
((())(()(())))()((())()()()(())()()(())()((()))()()((()()))((())())((())())(()())()(())(()(()))((()())())(()())((()()))(()()())((()))()())(()(()))((()()())(())()((())()))(())((())((())))(((()(())))()(())())(()(())(())())((())(())())((()(()))()()()()(()())())(((()))(())())((()())())((())()((()...

output:

18432

result:

ok single line: '18432'

Test #55:

score: 1
Accepted
time: 3ms
memory: 10048kb

input:

4000 5
(((((((()))(())(()(())()()(())(()))()()(((()))())()(()))(((()(()()))()())()()(()(())()(())))((()()()())(((())))((()())()(()()())()()()())()()(()(()))))())((()()())((((((()))()())(()())())())()((()()()(()()((()))()()())(())()())()()()))(())())()(((((()()(()(())()()))))((()()((())())((()())))((...

output:

4336

result:

ok single line: '4336'

Test #56:

score: 0
Wrong Answer
time: 0ms
memory: 10044kb

input:

4000 13
(((((()()))(()()(()((())(()()()))(()))(((()()(()()))()())((())()())()())((()()(())())((()()()()))(())()(())())()((()(())())()()()()())((()(()()()(()())))(()()))(((())(()()))()(())))))()((())((((()()())(()()))(())((()((())))())()(((())()()(()()())(()))()(((()))(((())()()(())))))(((()())))(()(...

output:

3926

result:

wrong answer 1st lines differ - expected: '3928', found: '3926'

Subtask #5:

score: 0
Wrong Answer

Test #75:

score: 0
Wrong Answer
time: 44ms
memory: 13628kb

input:

100000 3
(()((())(()))(())((()())))(((()()))(()))(()()()((())))()()((())(())((())(()(()))())((())))()()((())(()()))(((())))((())()(()())(()())()(()(()()())))(()(()()))()(()((())()()()()())((()))(())(())())(((()))()(()()())()(()()))((()()))(((()()()()))(()))(((())))(((()))(()()())(()(()()))(())(()())...

output:

3832015

result:

wrong answer 1st lines differ - expected: '3832013', found: '3832015'

Subtask #6:

score: 0
Wrong Answer

Test #89:

score: 1
Accepted
time: 49ms
memory: 13440kb

input:

100000 6
((((()()((())))()((()())()())((())()(((()()))())((())((()()()))()()()(())))(((()(())(()()))(())())(())))(((()))((((())))()))(()((())(())(())((()())))(()(()(()))(())(()()()(())())(()(())(()(()))(()())()((()))()()))(()()(())))((()())()((())((())()()(((()))(())))((())())()((()())(()))))()(((()...

output:

126039

result:

ok single line: '126039'

Test #90:

score: 1
Accepted
time: 49ms
memory: 13364kb

input:

100000 12
((()((())(((()))()())()()((()))())((((()()))()()))))(((())(()))(((((())))((())))(()()((()()()))((())()()((()(())((()))()()))())(()((()())())(()()(()))())()(()(())(())))()((()(()))((()))()((()()((())(())))))())(((()()))(()((()()))()(((()()()())()())))())(()((()())(())()(((()()))(()()()()))(...

output:

130680

result:

ok single line: '130680'

Test #91:

score: 1
Accepted
time: 44ms
memory: 11968kb

input:

100000 18
((())(()()()()())()()(())((())()()()())()()()()((()()())((()))()()(()())()()()())(()())()(()(())))(()()((()()))(())()()(()())()(()())((()())()()(())()())((())(()))(()()()))((())(()())()(((())))(()(()))(()(()))()(())()(((())())()()())((())))((()())((()())))((()))(()(()()()()((())))()(()))((...

output:

525576

result:

ok single line: '525576'

Test #92:

score: 1
Accepted
time: 42ms
memory: 13684kb

input:

100000 24
((((((())()((())))()()(())((()())())()()(((()))()()(((())))())(()())(()(()()(())((()())(()())))(()())()(()(())()())(()((()))))()(((()(()()))())())((()))()()(()(()))())((()()()()(()(()))(()))()(()))()(((()))(()()(()(()))())()((()()())()((())(())((())(())()()())()())((())))()((()())((()()()(...

output:

118587

result:

ok single line: '118587'

Test #93:

score: 0
Wrong Answer
time: 45ms
memory: 13628kb

input:

100000 30
((((())()()(((()()())())))((()))(())(()()(())))((())())((())(())())(((()(()(()))())(()())()()(())))(((()())(()))()((())((())()())((())()()()())()()()(())()()(()()))(((()()))(()()())(()(()()(())()))(())((())(()))(())()(()))))(((())(()()())()()((()))(()(()()()()((())))))((((()()()))(()((()))...

output:

132050

result:

wrong answer 1st lines differ - expected: '132047', found: '132050'

Subtask #7:

score: 0
Wrong Answer

Test #103:

score: 1
Accepted
time: 40ms
memory: 13188kb

input:

80000 81
((((((()())((()((()))))(()())()(()(((()(()())(()())())(())))()(())(()()))()))(((()(()))((()))(())((((())))(())()((()))())((()(()())))(())(()()))(((()()))(()((())))())()(((()()))(()())()()(((()((()))(())))((())(()((())))())(()())))()()()((()()(()()(())()()((()))(())()))((()(())()()))(()(()()...

output:

87799

result:

ok single line: '87799'

Test #104:

score: 0
Wrong Answer
time: 39ms
memory: 13160kb

input:

80000 729
(((())(()))(()()())(()(()))(()())(()()()())(((()()())))()(()()()(()())))(((())((()()())))())((()(())()()())((()()()))()(()()()())()()(((())(()))(()())()()()(())))((()))((()())()(()()())(()()()()())(())(((()))(()(()())())())(()()())(()(())()()()()(())())()())(((())()))(((()())(())()(())((()...

output:

76304

result:

wrong answer 1st lines differ - expected: '76309', found: '76304'

Subtask #8:

score: 0
Wrong Answer

Test #129:

score: 0
Wrong Answer
time: 36ms
memory: 12936kb

input:

79856 243
(())()(())(())(()()())()(())()(()())()(())()(())()((()))(())(()(())())()(()())()()(())(())((()()))(())(()()())(()())((()())()())(())()()(())()(())((()()))()()(()()())(())()()(()())(())(())((()))(())(())()()()()()(()(()))(()(())()(()))()()()()()()()()((()()))()()()()()(())()(())(()())()(()(...

output:

794575

result:

wrong answer 1st lines differ - expected: '794572', found: '794575'

Subtask #9:

score: 0
Wrong Answer

Test #155:

score: 1
Accepted
time: 45ms
memory: 13252kb

input:

99599 64
((((((()(((())()))))((((((()))()())())())(()(()(()())))(()(()()(())())((()(()()))((()))()(())()())()(()(())()((()()())()())()(((())()))(()))((())(()(())()))(()))())()(((())(((())()((())))())(()()(()))(()())()((())((()())()(())())(())()(())((())(()()(()))((()))(()()())))()(((()))(())))(())((...

output:

110447

result:

ok single line: '110447'

Test #156:

score: 1
Accepted
time: 45ms
memory: 13644kb

input:

100000 1024
((((((((()()))(((()()()(((())())))()(((())))((())()(()()())(()()))((()())(())()()))))(((((())())()))))(((((((()))))())(((())()()((())))((()()))())()(()()())((()()(((()))()())(()(()()))()((()(()))(())()(())()()(()())())()((()))(())())()()))())(((()()((()(())()))(()))((()())((()()()))()(()...

output:

74496

result:

ok single line: '74496'

Test #157:

score: 1
Accepted
time: 45ms
memory: 13668kb

input:

99065 16384
(((((((())((()())))()((())(((())))(()(())((()(()(()))))(()))())((()(((()())))()((())(())(()())(()()))((())()())(())(()(()(())(()))(()((()))))()(()))((()((()))()))()())(((()))(()(())())()(()(()(()(()()(())))(((())))))(((())(()())))(()()((()))()(())()((()))(()(())(())()))(()))(()(()))(()()...

output:

10056

result:

ok single line: '10056'

Test #158:

score: 1
Accepted
time: 45ms
memory: 13388kb

input:

100000 8
(((((())(())())(()()(()()))()((())()(())(())()))())()(((())(())())((())()))()((())(()()(((())))(()(()())(()())()))()(()(())()(()())())()()(()(())(()())))()(()((()()())()())((())))(()((()())(())()()(((())())()()()())()())(())(()))(((())()()())((())(())))((()()((())()()()))()(())((((()))()())...

output:

149395

result:

ok single line: '149395'

Test #159:

score: 0
Wrong Answer
time: 45ms
memory: 13368kb

input:

100000 144
(((((())(()(())()()(())())(((()))(()()))))()((()()(()())(())((()(()()(())))))(())(()()))((())((((()))()()(()))()())((())()())()()(()()()()(())(()()(())())))()((()(())()(()))()(()((()))())(()(()(()))))((()((()))()))((((()(()))((())()))())(((())(())()(((())())))()))((((())))()()(()()()())((...

output:

110182

result:

wrong answer 1st lines differ - expected: '110178', found: '110182'

Subtask #10:

score: 0
Wrong Answer

Test #181:

score: 0
Wrong Answer
time: 41ms
memory: 13564kb

input:

100000 256
((((())()(())())(((()))()((())()(()(())))))(((()(()))(((()))()()()()))()((((()))(())((()))))((()))(()((()()()()())()())(())(())()()(()()))(((()()))))())((((()))()((())()(()(())((()))))()((()()()()((()))))()(()(()()(()(())(()))))(())(((())))((()()((()))()())()())()((()())))()(((((()()))))(...

output:

107404

result:

wrong answer 1st lines differ - expected: '107402', found: '107404'