YEZAELP

SMMR-Chi-009: Maximum Subarray Sum

Dec 6th, 2021
782
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli N = 1e5 + 10;
  6. lli qs[N];
  7.  
  8. int main(){
  9.  
  10.     int n;
  11.     lli mod;
  12.     scanf("%d %lld", &n, &mod);
  13.    
  14.     for(int i=1;i<=n;i++){
  15.         scanf("%lld", &qs[i]);
  16.         qs[i] = (qs[i - 1] + qs[i]) % mod;
  17.     }
  18.  
  19.     set <lli> st;
  20.     lli mx = 0;
  21.     for(int i=1;i<=n;i++){
  22.         mx = max(mx, qs[i]);
  23.         auto it = st.upper_bound(qs[i]);
  24.         if(it != st.end())
  25.             mx = max(mx, (qs[i] - *it + mod) % mod);
  26.         st.insert({qs[i]});
  27.     }
  28.  
  29.     cout << mx;
  30.  
  31.     return 0;
  32. }
RAW Paste Data