fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define io {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
  4.  
  5. const int maxN=1e5;
  6. int N,K;
  7. long num[maxN];
  8.  
  9. deque<int> Q;
  10. int main() {
  11. io
  12. cin >> N >> K;
  13. num[0]=0;
  14. for(int i=1; i<=N; i++){
  15. cin >> num[i];
  16. num[i]+=num[i-1];
  17. }
  18. Q.push_back(0);
  19. long ans=0;
  20. for(int i=1; i<=N; i++){
  21. if(i-Q.front()>K){
  22. Q.pop_front();
  23. }
  24. while(!Q.empty() and num[Q.back()]>=num[i])
  25. Q.pop_back();
  26. Q.push_back(i);
  27. ans=max(ans,num[i]-num[Q.front()]);
  28. //cout << num[Q.front()] << ' ' << ans << '\n';
  29. }
  30. cout << ans;
  31. }
Success #stdin #stdout 0.01s 5432KB
stdin
10 4 
1 -5 7 2 5 -2 6 3 0 2 
stdout
14