Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1.  int n, k;
  2.   cin >> n >> k;
  3.   vector <int> a(n);
  4.   cin >> a;
  5.   vector <int> pref(n), suf(n);
  6.   pref[0] = a[0];
  7.   for (int i = 1; i < n; ++i)
  8.     pref[i] = pref[i - 1] + a[i];
  9.   suf.back() = a.back();
  10.   for (int i = n - 2; i >= 0; --i)
  11.     suf[i] = suf[i + 1] + a[i];
  12.   vector <int> left(n), right(n);
  13.   left[0] = pref[0];
  14.   for (int i = 1; i < k; ++i)
  15.     left[i] = left[i - 1] + a[i];
  16.   for (int i = k; i < n; ++i)
  17.   {
  18.     left[i] = left[i - 1];
  19.     int val = pref[i - 1] - (i - 1 - k >= 0 ? pref[i - 1 - k] : 0);
  20.     val += a[i];
  21.     val -= a[i - k];
  22.     left[i] = max(left[i], val);
  23.   }
  24.   right.back() = suf.back();
  25.   for (int i = n - 2; i >= n - k; --i)
  26.     right[i] = right[i + 1] + a[i];
  27.   for (int i = n - k - 1; i >= 0; --i)
  28.   {
  29.     right[i] = right[i + 1];
  30.     int val = suf[i + 1] - (i + 1 + k < n ? suf[i + 1 + k] : 0);
  31.     val += a[i];
  32.     val -= a[i + k];
  33.     right[i] = max(right[i], val);
  34.   }
  35.   int ans = right[k];
  36.   for (int i = k; i < n; ++i)
  37.   {
  38.     int val = max(left[i - k], i + 1 < n ? right[i + 1] : 0);
  39.     ans = min(ans, val);
  40.   }
  41.   cout << ans;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement