fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     // Optimize standard I/O operations for competitive programming
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.  
  10.     int n, k; 
  11.     if (!(cin >> n >> k)) return 0;
  12.  
  13.     vector<ll> a(n);
  14.     for(int i = 0; i < n; i++) {
  15.         cin >> a[i];
  16.     }
  17.  
  18.     // Calculate prefix sums
  19.     vector<ll> p(n);
  20.     p[0] = a[0];
  21.     for(int i = 1; i < n; i++) {
  22.         p[i] = a[i] + p[i-1];
  23.     }
  24.  
  25.     multiset<ll> u;
  26.     u.insert(0); // Essential for subarrays starting at index 0
  27.  
  28.     ll final_max = -1e18; // Use a very small number for negative arrays
  29.  
  30.     for(int i = 0; i < n; i++) {
  31.         // If the window size exceeds k, remove the oldest prefix sum
  32.         if(i >= k) {
  33.             ll val_to_remove = (i - k == 0) ? 0 : p[i - k - 1];
  34.             u.erase(u.find(val_to_remove));
  35.         }
  36.  
  37.         // The smallest prefix sum in the current window will yield the max subarray
  38.         ll r = p[i] - *u.begin();
  39.         final_max = max(final_max, r);
  40.  
  41.         // Insert the current prefix sum for future iterations
  42.         u.insert(p[i]);
  43.     }
  44.  
  45.     cout << final_max << "\n";
  46.  
  47.     return 0;
  48. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 4
-2 4 6 -2 8
stdout
copy 
16
https://ideone.com/wZbn2w
language:
C++ (gcc 8.3)
created:
20 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!