fork download
  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
stdin
5 2
3 6 1 1 6
stdout
1 4