Advertisement
JouJoy

I

Dec 12th, 2021
591
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <iostream>
  2. #include<valarray>
  3. #include<stdio.h>
  4. using namespace std;
  5. #define ll long long
  6. #define pb push_back
  7.  
  8. int main()
  9. {
  10.     int n, k;
  11.     cin >> n >> k;
  12.     ll a[n + 1] = { 0 };
  13.     for (int i = 1; i <= n; i++)
  14.         cin >> a[i];
  15.  
  16.     ll sum[n + 1] = { 0 };
  17.     for (int i = 1; i <= n; i++)
  18.         sum[i] = a[i] + sum[i - 1];
  19.  
  20.     ll dp[n - k] = { 0 };
  21.     for (int i = 1; i <= n - k + 1; i++)
  22.         dp[i] = sum[i + k - 1] - sum[i - 1];
  23.  
  24.     ll x = 0, mx = 0;
  25.     int l = 0, r = 0, y = 0;
  26.     for (int i = n - 2 * k + 1; i >= 1; i--)
  27.     {
  28.         if (x <= dp[i + k])
  29.         {
  30.             x = dp[i + k];
  31.             y = i + k;
  32.         }
  33.         if (x + dp[i] >= mx)
  34.         {
  35.             mx = x + dp[i];
  36.             l = i;
  37.             r = y;
  38.         }
  39.     }
  40.  
  41.     cout << l << " " << r << endl;
  42.  
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement