Advertisement
Fshl0

Untitled

Feb 21st, 2022
691
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 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 = 1e9 + 7;
  16. const int mxP = 1e2 + 9;
  17. const int mxN = 1e5 + 9;
  18. const int INF = 1e7 + 7;
  19. const int mxK = 20;
  20. const double eps = 1e-7;
  21.  
  22. ll A[mxN], dp[mxN], pre[mxN];
  23. vector <ll> idx[12];
  24. map <ll, ll> mp;
  25.  
  26. ll get (vector <ll>& v, ll x) {
  27.     int l = 0, r = v.size() - 1;
  28.     while (l != r) {
  29.         int mid = (l + r + 1) / 2;
  30.         if (v[mid] <= x)
  31.             l = mid;
  32.         else r = mid - 1;
  33.     }
  34.    
  35.     if (v[l] <= x)
  36.         return v[l];
  37.     return - 1;
  38. }
  39.  
  40. ll flex (ll x) {
  41.     return ((x % MOD) + MOD) % MOD;
  42. }
  43.  
  44. void solve () {
  45.     ll n;
  46.     cin >> n;
  47.    
  48.     for (int i = 1; i <= n; i++)
  49.         cin >> A[i];
  50.        
  51.     ll m;
  52.     cin >> m;
  53.    
  54.     for (int i = 1; i <= m; i++) {
  55.         ll x;
  56.         cin >> x;
  57.        
  58.         mp[x] = i;
  59.     }
  60.    
  61.     for (int i = 1; i <= n; i++) {
  62.         if (mp.count(A[i])) {
  63.             ll j = mp[A[i]];
  64.             idx[j].pb (i);
  65.         }
  66.     }
  67.    
  68.     for (ll i = 1; i <= n; i++) {
  69.         pre[i] = pre[i - 1] + A[i];
  70.         dp[i] = max (A[i], dp[i - 1] + A[i]);
  71.     }
  72.    
  73.     ll res = 0;
  74.     for (ll i = 1; i <= n; i++) {
  75.         ll L = n + 1;
  76.         for (auto [x, j]: mp)
  77.             L = min (L, get(idx[j], i));
  78.        
  79.         if (L == -1)
  80.             continue;
  81.        
  82.         res = max (res, pre[i] - pre[L - 1] + max (dp[L - 1], 0ll));
  83.     }
  84.    
  85.     cout << flex (res) << "\n";
  86.     return;
  87. }
  88.  
  89. int main () {
  90.     int t = 1;
  91.     //cin >> t;
  92.        
  93.     //preCalc ();
  94.     while (t--)
  95.         solve ();
  96.        
  97.     return 0;
  98. }
  99.  
  100. /*
  101.  11
  102. 1 2 -2 -1 6 -2 7 1 2 4 -100
  103. 2
  104. 2 1
  105.  * */
  106.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement