Advertisement
deushiro

Untitled

Jan 8th, 2020
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(0);
  11.     int n, k;
  12.     ll st = 0;
  13.     cin >> n >> k;
  14.     vector<ll> a(n);
  15.     vector<ll> s(n - k + 1);
  16.     vector<ll> pf(n - k + 1);
  17.     vector<ll> sf(n - k + 1);
  18.     for(int i = 0; i < n; ++i){
  19.         cin >> a[i];
  20.     }
  21.     for(int i = 0; i < k; ++i){
  22.         st += a[i];
  23.     }
  24.     s[0] = st;
  25.     for(int i = 1; i < n - k + 1; ++i){
  26.         s[i] = s[i - 1] + a[i + k - 1] - a[i - 1];
  27.     }
  28.     pf[0] = s[0];
  29.     sf.back() = s.back();
  30.     cout << "XD";
  31.     for(int i = 1; i < n; ++i){
  32.         pf[i] = max(s[i], pf[i - 1]);
  33.         sf[i] = max(s[i], sf[n - i]);
  34.     }
  35.     ll ans = 1e18;
  36.     for(int i = 0; i < n - k + 1; ++i){
  37.         if(i - k < 0)
  38.             ans = min(ans, sf[i + k]);
  39.         else if(i + k > n - 1)
  40.             ans = min(ans, pf[i - k]);
  41.         else
  42.             ans = min(ans, max(sf[i + k], pf[i - k]));
  43.     }
  44.     cout << ans << "\n";
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement