YEZAELP

o62_may11_insert

Nov 14th, 2021 (edited)
249
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 2e9;
  5. const int N = 2e5 + 10;
  6. vector <int> val;
  7. stack <int> st;
  8.  
  9. int main(){
  10.  
  11.     int n;
  12.     scanf("%d", &n);
  13.  
  14.     int num;
  15.     scanf("%d", &num);
  16.  
  17.     st.push(num);
  18.     for(int i=2;i<=n;i++){
  19.         char opr; scanf(" %c", &opr);
  20.         scanf("%d", &num);
  21.         num *= (opr == '-' ? -1: 1);
  22.         if(num < 0){
  23.             if(!st.empty()){
  24.                 val.push_back(st.top());
  25.                 st.pop();
  26.             }
  27.             val.push_back(num);
  28.         }
  29.         else{
  30.             int tp = 0;
  31.             if(!st.empty()){
  32.                 tp = st.top();
  33.                 st.pop();
  34.             }
  35.             st.push(tp + num);
  36.         }
  37.  
  38.     }
  39.  
  40.     if(!st.empty()){
  41.         val.push_back(st.top());
  42.         st.pop();
  43.     }
  44.  
  45.     int sz = val.size();
  46.     vector <int> qs_abs(sz + 10, 0);
  47.  
  48.     for(int i=sz-1;i>=0;i--)
  49.         qs_abs[i] = qs_abs[i+1] + abs(val[i]);
  50.  
  51.     int sum = 0, ans = 0;
  52.     for(int i=0;i<sz;i++){
  53.         sum += val[i];
  54.         ans = max(ans, sum);
  55.         if(val[i] < 0 and i + 2 < sz)
  56.             ans = max(ans, sum - val[i+1] + qs_abs[i+2]);
  57.     }
  58.  
  59.     printf("%d", ans);
  60.  
  61.     return 0;
  62. }
Add Comment
Please, Sign In to add comment