fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <cmath>
  9. #include <algorithm>
  10.  
  11. #define MAXN 200000
  12.  
  13. using namespace std;
  14.  
  15. long long input[MAXN + 2],
  16.           sum[MAXN + 2];
  17.  
  18. int main() {
  19.     #ifdef mahfuz
  20.     freopen("input", "r", stdin);
  21.     #endif
  22.  
  23.     int n, k;
  24.     long long r, sum_sofar, l, a, b, maxb;
  25.     cin >> n >> k;
  26.  
  27.     cin >> input[0];
  28.     sum[0] = input[0];
  29.  
  30.     for(int i = 1; i < n; i++) {
  31.         cin >> input[i];
  32.         sum[i] = sum[i - 1] + input[i];
  33.     }
  34.  
  35.     r = sum[n - 1] - sum[n - k - 1];
  36.     sum_sofar = sum[n - 1] - sum[n - 2*k - 1];
  37.  
  38.     for(int i = n - 2 * k; i >= 0; i--) {
  39.         if(r <= sum[i + 2*k - 1] - sum[i + k - 1]) {
  40.             r = sum[i + 2*k - 1] - sum[i + k - 1];
  41.             maxb = i + k;
  42.         }
  43.  
  44.         //r = max(r, sum[i + 2*k - 1] - sum[i + k - 1]);
  45.         l = sum[i + k - 1] - sum[i  - 1];
  46.  
  47.         if(sum_sofar <= l + r) {
  48.             sum_sofar = l + r;
  49.             a = i;
  50.             b = maxb;
  51.         }
  52.  
  53.         //cout << i << " " << l << " " << r << " " << sum_sofar << endl;
  54.     }
  55.  
  56.     cout << a + 1 << " " << b + 1 << endl;
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 5980KB
comments (?)
stdin
copy 
5 2
3 6 1 1 6
stdout
copy 
1 4
https://ideone.com/cTqaKy
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!