fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. #define __PhucSama__ signed main()
  5. #define RyoikiTenkai ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define FukumaMizushi(file) freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
  7.  
  8. #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
  9.  
  10. #define el cout << "\n"
  11. #define pb push_back
  12. #define ll long long
  13. #define pli pair<ll, int>
  14. #define fi first
  15. #define se second
  16.  
  17. using namespace std;
  18.  
  19. const int N = 3e6 + 7;
  20. const ll INF = 1e18 + 7;
  21. int n, k, a[N];
  22. ll dp[N], pref[N];
  23. deque<pli> deq;
  24. ll res;
  25.  
  26. void input() {
  27.     cin >> n >> k;
  28.     FOR(i, 1, n) cin >> a[i], pref[i] = pref[i - 1] + a[i];
  29. }
  30.  
  31. void solve() {
  32.     deq.pb({0, 0});
  33.     FOR(i, 1, n) {
  34.         while (!deq.empty() && deq.front().se < i - k + 1) deq.pop_front();
  35.         ll preMax = deq.empty() ? -INF : deq.front().fi;    
  36.         dp[i] = max(dp[i - 1], preMax + pref[i]);    
  37.         res = max(res, dp[i]);
  38.         ll add = dp[i - 1] - pref[i];
  39.         while (!deq.empty() && deq.back().fi <= add) deq.pop_back();
  40.         deq.pb({add, i});
  41.     }
  42.     cout << res;
  43. }
  44.  
  45. __PhucSama__ {
  46.     RyoikiTenkai; 
  47.     // FukumaMizushi("Test"); 
  48.     input();
  49.     solve();
  50.     return 0 ^ 0;
  51. }
  52.  
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nmve6e
language:
C++14 (gcc 8.3)
created:
17 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!