1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| #include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i <= (e); ++i)
#define fep(i, s, e) for(int i = s; i < (e); ++i)
#define _rep(i, s, e) for(int i = s; i >= (e); --i)
#define _fep(i, s, e) for(int i = s; i > (e); --i)
#define int long long
#define pii pair<int, int>
using namespace std;
constexpr int inf = numeric_limits<int>::max() >> 1;
constexpr int ninf = numeric_limits<int>::min() >> 1;
constexpr int mod = 998244353;
constexpr double eps = 1e-9;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, a[400005], b[400005], ans;
string s;
struct Vector { int x, y; };
inline Vector operator+(const Vector &x, const Vector &y) { return {x.x + y.x, x.y + y.y}; }
inline bool operator<(const Vector &x, const Vector &y) { return __int128(1) * x.y * y.x < __int128(1) * y.y * x.x; }
inline bool operator>(const Vector &x, const Vector &y) { return __int128(1) * x.y * y.x > __int128(1) * y.y * x.x; }
inline bool operator<=(const Vector &x, const Vector &y) { return __int128(1) * x.y * y.x <= __int128(1) * y.y * x.x; }
inline bool operator==(const Vector &x, const Vector &y) { return __int128(1) * x.y * y.x == __int128(1) * y.y * x.x; }
inline bool operator>=(const Vector &x, const Vector &y) { return __int128(1) * x.y * y.x >= __int128(1) * y.y * x.x; }
struct Treap {
struct Node {
Vector val, sum;
int sz, lz, key, ls, rs;
} tr[400005];
int rt, cnt;
inline void update(int p, int d) {
if(not p) return;
tr[p].sum.y += d * tr[p].sum.x;
tr[p].val.y += d * tr[p].val.x;
tr[p].lz += d;
}
inline void pushdown(int p) {
if(tr[p].lz) {
update(tr[p].ls, tr[p].lz);
update(tr[p].rs, tr[p].lz);
tr[p].lz = 0;
}
}
inline void pushup(int p) {
tr[p].sum = tr[tr[p].ls].sum + tr[tr[p].rs].sum + tr[p].val;
tr[p].sz = tr[tr[p].ls].sz + tr[tr[p].rs].sz + 1;
}
inline int create(const Vector &d) {
++cnt, tr[cnt].val = tr[cnt].sum = d, tr[cnt].sz = 1;
tr[cnt].lz = tr[cnt].ls = tr[cnt].rs = 0, tr[cnt].key = rnd();
return cnt;
}
int merge(int p, int q) {
if(not p or not q) return p | q; pushdown(p), pushdown(q);
if(tr[p].key < tr[q].key) return tr[p].rs = merge(tr[p].rs, q), pushup(p), p;
else return tr[q].ls = merge(p, tr[q].ls), pushup(q), q;
}
void split(int p, const Vector &d, int &x, int &y) {
if(not p) return x = y = 0, void(); pushdown(p);
if(tr[p].val > d) split(tr[p].rs, d, tr[x = p].rs, y);
else split(tr[p].ls, d, x, tr[y = p].ls);
pushup(p);
}
void split(int p, int d, int &x, int &y) {
if(not p) return x = y = 0, void(); pushdown(p);
int t = tr[tr[p].ls].sum.x + tr[p].val.x;
if(d >= t) split(tr[p].rs, d - t, tr[x = p].rs, y);
else split(tr[p].ls, d, x, tr[y = p].ls);
pushup(p);
}
void split1(int p, const Vector &d, int &x, int &y) {
if(not p) return x = y = 0, void(); pushdown(p);
if(tr[p].val > tr[tr[p].rs].sum + d) split1(tr[p].rs, d, tr[x = p].rs, y);
else split1(tr[p].ls, tr[tr[p].rs].sum + d, x, tr[y = p].ls);
pushup(p);
}
inline Vector query(int p) {
while(tr[p].ls) pushdown(p), p = tr[p].ls;
return tr[p].val;
}
void update(int p, const Vector &d) {
pushdown(p);
if(tr[p].ls) update(tr[p].ls, d);
else tr[p].val = d;
pushup(p);
}
inline void insert(const Vector &d) {
int x, y; split(rt, d, x, y);
rt = merge(merge(x, create(d)), y);
}
inline void operate(int d) {
if(tr[rt].sum.x <= d) return ans += d, update(rt, -1);
int x, y, z; split(rt, d, x, z);
Vector w = query(z);
w.y -= d - tr[x].sum.x;
ans += d, update(x, -1);
split1(x, w, x, y);
update(z, tr[y].sum + w);
rt = merge(x, z);
}
int query(int p, int d) {
if(not p) return 0;
pushdown(p);
int t = d + tr[tr[p].ls].sum.y + tr[p].val.y;
return max(t, max(query(tr[p].ls, d), query(tr[p].rs, t)));
}
} tr;
void solve() {
cin >> n >> s, tr.rt = tr.cnt = ans = 0, tr.tr[0] = {};
rep(i, 1, n) cin >> a[i];
rep(i, 1, n) cin >> b[i], ans += b[i], a[i] -= b[i];
rep(i, 1, n) if(a[i] > 0) {
if(s[i - 1] == '1') tr.insert({1, a[i]});
else tr.operate(a[i]);
}
cout << ans + tr.query(tr.rt, 0) << '\n';
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1; cin >> T;
while(T--) solve();
return 0;
}
|
