Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
- using namespace std;
- typedef long long ll;
- const int MOD = 998244353;
- const int mxN = 1e5 + 9;
- const int mxM = 1e5 + 9;
- const ll INF = 1e17 + 7;
- const double eps = 1e-7;
- ll segTree[8 * mxN], dp[mxN], preC[mxN], preA[mxN];
- int A[mxN], C[mxN];
- void updateTree (int v, int l, int r, int idx, ll val) {
- if (l == r) {
- segTree[v] = min (segTree[v], val);
- return;
- }
- int mid = (l + r) / 2;
- if (idx <= mid)
- updateTree (2 * v, l, mid, idx, val);
- else updateTree (2 * v + 1, mid + 1, r, idx, val);
- segTree[v] = min(segTree[2 * v], segTree[2 * v + 1]);
- return;
- }
- ll getMin (int v, int l, int r, int L, int R) {
- if (R < L)
- return INF;
- if (L <= l && r <= R)
- return segTree[v];
- if (l > R || r < L)
- return 0;
- int mid = (l + r) / 2;
- ll leftMin = getMin (2 * v, l, mid, L, R);
- ll rightMin = getMin (2 * v + 1, mid + 1, r, L, R);
- return min (leftMin, rightMin);
- }
- void buildTree (int v, int l, int r) {
- if (l == r) {
- segTree[v] = INF;
- return;
- }
- int mid = (l + r) / 2;
- buildTree (2 * v, l, mid);
- buildTree (2 * v + 1, mid + 1, r);
- segTree[v] = INF;
- }
- void solve () {
- int n, k;
- cin >> n >> k;
- for (int i = 1; i <= n; i++)
- cin >> A[i];
- for (int i = 1; i <= n; i++) {
- cin >> C[i];
- int sign = (C[i] == 2) ? 1 : -1;
- preA[i] = preA[i - 1] + A[i];
- preC[i] = preC[i - 1] + sign * C[i];
- }
- buildTree (1, 0, 2 * n);
- updateTree (1, 0, 2 * n, 0, 0);
- for (int r = 1; r <= n; r++) {
- preC[r] += n;
- int L = preC[r] - k, R = preC[r] + k;
- ll query = getMin (1, 0, 2 * n, max (L, 0), min (R, 2 * n));
- if (query == INF)
- dp[r] = -INF;
- else dp[r] = preA[r] - query;
- updateTree (1, 0, 2 * n, preC[r], preA[r]);
- }
- ll res = 0;
- for (int i = 1; i <= n; i++)
- res = max (res, dp[i]);
- cout << res << "\n";
- return ;
- }
- int main () {
- int t = 1;
- //cin >> t;
- //preCalc ();
- while (t--)
- solve ();
- return 0;
- }
- /*
- *
- 10 0
- -1000 1
- -100 2
- -10 1
- 1 2
- 2 1
- 3 2
- -100 1
- 2 2
- 5 2
- -1000 2
- *
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement