Advertisement
deushiro

Untitled

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