Advertisement
Ahmed_Negm

Untitled

Apr 9th, 2024
626
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define nl "\n"
  6.  
  7. void files(){
  8.     ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
  9.     #ifndef ONLINE_JUDGE
  10.         freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  11.     #endif
  12. }
  13.  
  14.  
  15. void solve(){
  16.     ll n,m; cin>>n>>m;
  17.     vector<ll> v(n+1);
  18.     vector<ll> pre(n+2), suf(n+2);
  19.     for(ll i=1; i<=n; i++) cin>>v[i];
  20.     vector<pair<int,int>> intervals;
  21.  
  22.     for(int i=1; i<=n; i++) pre[i] = pre[i-1] + v[i];
  23.     for(int i=n; i>=1; i--) suf[i] = suf[i+1] + v[i];
  24.  
  25.     unordered_map<ll,int>mp;
  26.  
  27.     auto add = [&](int i){
  28.         if(mp[v[i]] == 0) m--;
  29.         mp[v[i]]++;
  30.     };
  31.  
  32.     auto remove = [&](int i){
  33.         mp[v[i]]--;
  34.         if(mp[v[i]] == 0) m++;
  35.     };
  36.  
  37.     int l=1,r=1;
  38.     while(r<=n){
  39.         add(r);
  40.         while(m <= 0){
  41.             if(m == 0) intervals.push_back({l,r});
  42.             remove(l);
  43.             l++;
  44.         }
  45.         r++;
  46.     }
  47.  
  48.  
  49.  
  50.     set<int> pos;
  51.     if(v[1]>0) pos.insert(1);
  52.     if(v[n]>0) pos.insert(n);
  53.     for(int i=1;i<=n;i++){
  54.         if(v[i]<0){
  55.             if(i>1 and v[i-1]>0) pos.insert(i-1);
  56.             if(i<n and v[i+1]>0) pos.insert(i+1);
  57.         }
  58.     }
  59.  
  60.     vector<ll> inc(pos.begin(),pos.end());
  61.     ll ans = LONG_LONG_MIN;
  62.     for(auto&[f,s]:intervals){
  63.         ll sum = pre[s]-pre[f-1];
  64.         ll tmp1 = sum;
  65.         int idx1 = upper_bound(inc.begin(),inc.end(),s)-inc.begin();
  66.         for(int i=0;i<(int)inc.size();i++){
  67.             if(inc[i]>=f) break;
  68.             for(int j=idx1;j<(int)inc.size();j++){
  69.                 ll left = pre[f-1] - pre[inc[i]-1];
  70.                 ll right = pre[inc[j]] - pre[s];
  71.                 tmp1 = max(tmp1,sum+left+right);
  72.             }
  73.         }
  74.  
  75.         for(int i=0;i<(int)inc.size();i++){
  76.             if(inc[i]>= f and inc[i]<=s) continue;
  77.             if(inc[i]<f){
  78.                 ll left = pre[f-1] - pre[inc[i]-1];
  79.                 tmp1 = max(tmp1,sum+left);
  80.             }else{
  81.                 ll right = pre[inc[i]] - pre[s];
  82.                 tmp1 = max(tmp1,sum+right);
  83.             }
  84.         }
  85.  
  86.         ans = max(ans,tmp1);
  87.     }
  88.  
  89.     cout<<ans<<nl;
  90.  
  91. }
  92.  
  93. int main(){
  94.     files();
  95.     int t = 1;
  96.     cin>>t;
  97.     while(t--) solve();
  98.  
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement