raghuvanshraj

689.cpp

Jul 26th, 2021
799
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  03.06.2020 10:50:06 AM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. vector<int> maxSumOfThreeSubarrays(vector<int> &arr, int k) {
  10.     int n = arr.size();
  11.     int sum = accumulate(arr.begin(), arr.begin() + k - 1, 0);
  12.     vector<int> sums(n - k + 1);
  13.     for (int i = k - 1; i <= n - 1; ++i) {
  14.         sum += arr[i];
  15.         sums[i - k + 1] = sum;
  16.         sum -= arr[i - k + 1];
  17.     }
  18.  
  19.     vector<int> left(n - k + 1), right(n - k + 1);
  20.     int curr_max = INT_MIN;
  21.     int idx = -1;
  22.     for (int i = 0; i <= n - k; ++i) {
  23.         if (curr_max < sums[i]) {
  24.             curr_max = sums[i];
  25.             idx = i;
  26.         }
  27.  
  28.         left[i] = idx;
  29.     }
  30.  
  31.     curr_max = INT_MIN;
  32.     idx = -1;
  33.     for (int i = n - k; i >= 0; --i) {
  34.         if (curr_max <= sums[i]) {
  35.             curr_max = sums[i];
  36.             idx = i;
  37.         }
  38.  
  39.         right[i] = idx;
  40.     }
  41.  
  42.     int left_idx = -1, right_idx = -1, middle_idx = -1;
  43.     int ans = INT_MIN;
  44.     for (int i = k; i <= n - 2 * k; ++i) {
  45.         int curr_ans = sums[left[i - k]] + sums[i] + sums[right[i + k]];
  46.         if (ans < curr_ans) {
  47.             left_idx = left[i - k];
  48.             right_idx = right[i + k];
  49.             middle_idx = i;
  50.  
  51.             ans = curr_ans;
  52.         }
  53.     }
  54.  
  55.     return {left_idx, middle_idx, right_idx};
  56. }
  57.  
  58. int main(int argc, char const *argv[]) {
  59.     int n, k;
  60.     cin >> n >> k;
  61.     vector<int> arr(n);
  62.     for (int i = 0; i <= n - 1; ++i) {
  63.         cin >> arr[i];
  64.     }
  65.  
  66.     vector<int> ans = maxSumOfThreeSubarrays(arr, k);
  67.     for (int i = 0; i <= 2; ++i) {
  68.         cout << ans[i] << ' ';
  69.     }
  70.  
  71.     return 0;
  72. }
RAW Paste Data