Advertisement
Fshl0

Untitled

Feb 28th, 2022
1,456
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb push_back
  5.  
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9.  
  10. #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
  11.  
  12. using namespace std;
  13. typedef long long ll;
  14.  
  15. const int MOD = 998244353;
  16. const int mxN = 1e5 + 9;
  17. const int mxM = 1e5 + 9;
  18. const ll INF = 1e17 + 7;
  19. const double eps = 1e-7;
  20.  
  21. ll segTree[8 * mxN], dp[mxN], preC[mxN], preA[mxN];
  22. int A[mxN], C[mxN];
  23.  
  24. void updateTree (int v, int l, int r, int idx, ll val) {
  25.     if (l == r) {
  26.         segTree[v] = min (segTree[v], val);
  27.        
  28.         return;
  29.     }
  30.    
  31.     int mid = (l + r) / 2;
  32.     if (idx <= mid)
  33.         updateTree (2 * v, l, mid, idx, val);
  34.     else updateTree (2 * v + 1, mid + 1, r, idx, val);
  35.    
  36.     segTree[v] = min(segTree[2 * v], segTree[2 * v + 1]);
  37.     return;
  38. }
  39.  
  40. ll getMin (int v, int l, int r, int L, int R) {
  41.     if (R < L)
  42.         return INF;
  43.    
  44.     if (L <= l && r <= R)
  45.         return segTree[v];
  46.    
  47.     if (l > R || r < L)
  48.         return 0;
  49.    
  50.     int mid = (l + r) / 2;
  51.     ll leftMin = getMin (2 * v, l, mid, L, R);
  52.     ll rightMin = getMin (2 * v + 1, mid + 1, r, L, R);
  53.    
  54.     return min (leftMin, rightMin);
  55. }
  56.  
  57. void buildTree (int v, int l, int r) {
  58.     if (l == r) {
  59.         segTree[v] = INF;
  60.        
  61.         return;
  62.     }
  63.    
  64.     int mid = (l + r) / 2;
  65.     buildTree (2 * v, l, mid);
  66.     buildTree (2 * v + 1, mid + 1, r);
  67.    
  68.     segTree[v] = INF;
  69. }
  70.  
  71. void solve () {
  72.     int n, k;
  73.     cin >> n >> k;
  74.    
  75.     for (int i = 1; i <= n; i++)
  76.         cin >> A[i];
  77.    
  78.     for (int i = 1; i <= n; i++) {
  79.         cin >> C[i];
  80.        
  81.         int sign = (C[i] == 2) ? 1 : -1;
  82.        
  83.         preA[i] = preA[i - 1] + A[i];
  84.         preC[i] = preC[i - 1] + sign * C[i];
  85.     }
  86.    
  87.     buildTree (1, 0, 2 * n);
  88.     updateTree (1, 0, 2 * n, 0, 0);
  89.    
  90.     for (int r = 1; r <= n; r++) {
  91.         preC[r] += n;
  92.         int L = preC[r] - k, R = preC[r] + k;
  93.        
  94.         ll query = getMin (1, 0, 2 * n, max (L, 0), min (R, 2 * n));
  95.         if (query == INF)
  96.             dp[r] = -INF;
  97.         else dp[r] = preA[r] - query;
  98.        
  99.         updateTree (1, 0, 2 * n, preC[r], preA[r]);
  100.     }
  101.    
  102.     ll res = 0;
  103.     for (int i = 1; i <= n; i++)
  104.         res = max (res, dp[i]);
  105.        
  106.     cout << res << "\n";
  107.     return ;
  108. }
  109.  
  110. int main () {
  111.     int t = 1;
  112.     //cin >> t;
  113.        
  114.     //preCalc ();
  115.     while (t--)
  116.         solve ();
  117.        
  118.     return 0;
  119. }
  120.  
  121. /*
  122.  *
  123. 10 0
  124. -1000 1
  125. -100 2
  126. -10 1
  127. 1 2
  128. 2 1
  129. 3 2
  130. -100 1
  131. 2 2
  132. 5 2
  133. -1000 2
  134.  
  135.  
  136.  *
  137.  */
  138.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement