QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71847 | #4053. 序列变换 | He_Ren | 100 ✓ | 91ms | 13788kb | C++17 | 2.6kb | 2023-01-12 01:58:23 | 2023-01-12 01:58:24 |
Judging History
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