QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71847#4053. 序列变换He_Ren100 ✓91ms13788kbC++172.6kb2023-01-12 01:58:232023-01-12 01:58:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-12 01:58:24]
  • 评测
  • 测评结果:100
  • 用时:91ms
  • 内存:13788kb
  • [2023-01-12 01:58:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5 + 5;
const int inf = 0x3f3f3f3f;

inline int read(void)
{
	int res=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') res=res*10+c-'0', c=getchar();
	return res;
}

char s[MAXN * 2];
int a[MAXN], dep[MAXN];

int main(void)
{
//	freopen("bracket.in","r",stdin);
//	freopen("bracket.out","w",stdout);
	
	int n = read(), X = read(), Y = read();
	scanf("%s",s+1);
	for(int i=1; i<=n; ++i) a[i] = read();
	
	if(X == 0 && Y == 0)
	{
		printf("0");
		return 0;
	}
	
	{
		int curdep = 0, curid = 0;
		for(int i=1; i<=2*n; ++i)
		{
			if(s[i] == '(')
				dep[++curid] = curdep++;
			else --curdep;
		}
	}
	
	if(X == 1 && Y == 0)
	{
		static int siz[MAXN];
		for(int i=1; i<=n; ++i) ++siz[dep[i]];
		for(int i=1; i<n-1; ++i) siz[i] += siz[i-1];
		for(int i=0; i<n-1; ++i) siz[i] -= i;
		
		int beg = 0;
		while(beg<n && siz[beg] == 1) ++beg;
		if(beg == n)
		{
			printf("0");
			return 0;
		}
		
		int mid = beg;
		while(siz[mid] == 2) ++mid;
		
		static int mn[MAXN], mx[MAXN];
		memset(mn, 0x3f, sizeof(mn));
		memset(mx, 0xc0, sizeof(mx));
		for(int i=1; i<=n; ++i)
		{
			mn[dep[i]] = min(mn[dep[i]], a[i]);
			mx[dep[i]] = max(mx[dep[i]], a[i]);
		}
		
		auto getres = [&] (int x,int y) -> ll
		{
			ll cur = 0;
			for(int i=mid; i<n-1; ++i)
			{
				x = min(x, mn[i]);
				y = max(y, mx[i]);
				cur += (ll)x * (siz[i] - 2);
			}
			return cur - y;
		};
		
		int x = inf, y = -inf;
		for(int i=beg; i<mid; ++i)
		{
			x = min(x, mn[i]);
			y = max(y, mx[i]);
		}
		
		ll ans;
		if(beg == mid) ans = getres(x, y);
		else ans = min(getres(x, x), getres(y, y));
		
		for(int i=1; i<=n; ++i) if(dep[i] >= beg)
			ans += a[i];
		printf("%lld",ans);
		return 0;
	}
	else
	{
		static int id[MAXN];
		iota(id+1, id+n+1, 1);
		sort(id+1, id+n+1, [&] (int x,int y){
			return dep[x] < dep[y];
		});
		
		ll ans = 0;
		priority_queue<int> t;
		ll sum = 0;
		int mn = -1;
		for(int rt=0, ut=1; rt<n; ++rt)
		{
			while(ut<=n && dep[id[ut]] <= rt)
			{
				int u = id[ut++];
				t.push(a[u]); sum += a[u];
				
				if((int)t.size() == 1) mn = a[u];
				else mn = min(mn, a[u]);
			}
			
			int mx = t.top();
			if(X == 0)// X == 0, Y == 1
			{
				ans += sum - mx;
				sum -= mx; t.pop();
			}
			else// X == 1, Y == 1
			{
				ans += sum - mn;
				ans += (ll)mn * ((int)t.size() - 1);
				sum -= mx; t.pop();
			}
		}
		printf("%lld",ans);
		return 0;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4
Accepted
time: 0ms
memory: 12148kb

input:

8 1 0
((((())()()))())
9885387 6516650 9760493 9641422 5202363 4238336 7747794 490028

output:

36405804

result:

ok 1 number(s): "36405804"

Test #2:

score: 4
Accepted
time: 2ms
memory: 10072kb

input:

8 1 0
((((()()())))())
9885387 9641422 7747794 9760493 5202363 6516650 4636916 4238336

output:

51894229

result:

ok 1 number(s): "51894229"

Test #3:

score: 4
Accepted
time: 3ms
memory: 7744kb

input:

8 1 1
(((()())()()))()
9885387 5202363 490028 3368691 9641422 6516650 9760493 4238336

output:

99314759

result:

ok 1 number(s): "99314759"

Test #4:

score: 4
Accepted
time: 22ms
memory: 13100kb

input:

400000 1 0
((((()(()())(())(()((((()(()(()))))))(()()(())()(())(()()((())(()))())(()(()(()(())(())()))(()((()))())((())()()()(()(()(())(()())((())((()(())))((()))(()((()())))))(()(()()((()))())(()()())(((()()))(()(())((())))((()()))(()()(()))))((())(())((())())(()()(()))))((())()(()()()(()()())))(()...

output:

398732254583021874

result:

ok 1 number(s): "398732254583021874"

Test #5:

score: 4
Accepted
time: 40ms
memory: 12436kb

input:

400000 1 1
(()(()())(())(()((((()(()(()))))))(()()(())()(())(()()((())(()))())(()(()(()(())(())()))(()((()))())((())()()()(()(()(())(()())((())((()(())))((()))(()((()())))))(()(()()((()))())(()()())(((()()))(()(())((())))((()()))(()()(()))))((())(())((())())(()()(()))))((())()(()()()(()()())))(()()(...

output:

1277445719345875816

result:

ok 1 number(s): "1277445719345875816"

Test #6:

score: 4
Accepted
time: 5ms
memory: 10844kb

input:

20 1 0
((((((((((((((((()()())))))))))))))())))
9885387 9760493 9641422 3455737 1595369 2520060 5202363 383427 5005212 7513927 4238336 7747794 4702568 490028 5180541 4636916 4089173 4897764 3368691 6516650

output:

67797073

result:

ok 1 number(s): "67797073"

Test #7:

score: 4
Accepted
time: 4ms
memory: 10208kb

input:

20 1 0
(((((((((())()((())))()(()(()))))))())))
8722863 8703136 7513927 3665124 6956430 1979803 5174068 2520060 1595369 4089173 383427 4702568 3368691 6465783 5180541 1021531 3455737 5005212 4897764 1513930

output:

76233193

result:

ok 1 number(s): "76233193"

Test #8:

score: 4
Accepted
time: 0ms
memory: 5620kb

input:

20 1 1
(((((()((())()(((()))))()(()(()))))))())
8722863 5634023 1513930 4897764 8703136 4089173 1021531 383427 4702568 3455737 5180541 6956430 6465783 5005212 7513927 1979803 3665124 5723059 1595369 5174068

output:

314768566

result:

ok 1 number(s): "314768566"

Test #9:

score: 4
Accepted
time: 51ms
memory: 9984kb

input:

350000 0 1
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

26841786325208686

result:

ok 1 number(s): "26841786325208686"

Test #10:

score: 4
Accepted
time: 68ms
memory: 11768kb

input:

400000 0 1
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

28037973526177667

result:

ok 1 number(s): "28037973526177667"

Test #11:

score: 4
Accepted
time: 91ms
memory: 10700kb

input:

400000 0 1
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

178128920485682222

result:

ok 1 number(s): "178128920485682222"

Test #12:

score: 4
Accepted
time: 53ms
memory: 10344kb

input:

400000 0 1
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

81004444

result:

ok 1 number(s): "81004444"

Test #13:

score: 4
Accepted
time: 3ms
memory: 11452kb

input:

2000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

11784741323

result:

ok 1 number(s): "11784741323"

Test #14:

score: 4
Accepted
time: 3ms
memory: 11820kb

input:

2000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

11784741323

result:

ok 1 number(s): "11784741323"

Test #15:

score: 4
Accepted
time: 0ms
memory: 9784kb

input:

2000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

2428581049

result:

ok 1 number(s): "2428581049"

Test #16:

score: 4
Accepted
time: 3ms
memory: 5696kb

input:

2000 1 1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()(()())((())(()()()))(()()((())()(()()()(((()))))(()(()(()(())())))()((())))(()(()(())))((())(()())(()(())((()))(()(())(()))...

output:

5495819380766

result:

ok 1 number(s): "5495819380766"

Test #17:

score: 4
Accepted
time: 22ms
memory: 13184kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

19998495457

result:

ok 1 number(s): "19998495457"

Test #18:

score: 4
Accepted
time: 11ms
memory: 13756kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

19998783786

result:

ok 1 number(s): "19998783786"

Test #19:

score: 4
Accepted
time: 13ms
memory: 13788kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

19998749017

result:

ok 1 number(s): "19998749017"

Test #20:

score: 4
Accepted
time: 15ms
memory: 12540kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

19998573314

result:

ok 1 number(s): "19998573314"

Test #21:

score: 4
Accepted
time: 24ms
memory: 12668kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

19998540124

result:

ok 1 number(s): "19998540124"

Test #22:

score: 4
Accepted
time: 15ms
memory: 13776kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1263574956069

result:

ok 1 number(s): "1263574956069"

Test #23:

score: 4
Accepted
time: 22ms
memory: 12332kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1581722851072

result:

ok 1 number(s): "1581722851072"

Test #24:

score: 4
Accepted
time: 20ms
memory: 13356kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1243099504352

result:

ok 1 number(s): "1243099504352"

Test #25:

score: 4
Accepted
time: 16ms
memory: 13752kb

input:

400000 1 0
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1140371996503

result:

ok 1 number(s): "1140371996503"

Extra Test:

score: 0
Extra Test Passed