fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5.  
  6. int main() {
  7.     ll n, k;
  8.     cin >> n >> k;
  9.  
  10.     vector<ll> b(n);  // 0-based indexing
  11.     for (int i = 0; i < n; ++i) {
  12.         cin >> b[i];
  13.     }
  14.  
  15.     vector<ll> p(n, 0);  // Prefix sum array of size n
  16.  
  17.     p[0] = b[0];  // Initialize first prefix sum
  18.     for (int i = 1; i < n; ++i) {
  19.         p[i] = b[i] + p[i - 1];  // Compute prefix sum
  20.     }
  21.  
  22.     ll final_ans = -1e18;
  23.     multiset<ll> u;
  24.  
  25.     for (int j = 0; j < n; ++j) {
  26.         ll r = -1e18;
  27.  
  28.         if (j - k >= 0) {
  29.             u.erase(u.find(p[j - k]));  // Remove outdated prefix sum
  30.         }
  31.  
  32.         if (!u.empty()) {
  33.             r = p[j] - *u.begin();  // Compute max subarray sum
  34.         } else {
  35.             r = p[j];  // If no previous sums, take p[j] as the subarray sum
  36.         }
  37.  
  38.         final_ans = max(final_ans, r);
  39.         u.insert(p[j]);
  40.     }
  41.  
  42.     cout << final_ans << endl;
  43.  
  44.     return 0;
  45. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
6 4 
-3 4 3 -2 2 5
stdout
copy 
7
https://ideone.com/y1l8cs
language:
C++14 (gcc 8.3)
created:
10 days 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!