vadimk772336

Untitled

Sep 23rd, 2021
475
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void printArray(int* array, int L, int R)
  5. {
  6.     for (int i = L; i <= R; ++i)
  7.         std::cout << array[i] << " ";
  8.     std::cout << endl;
  9. }
  10.  
  11. int partition(int* array, int* ind_array, int l, int r)
  12. {
  13.     int i, j, tmp, tmp_ind, pivot;
  14.     pivot = array[(l + r) / 2];
  15.     tmp = 0;
  16.  
  17.     while (true) {
  18.         while (array[l] < pivot)
  19.             l += 1;
  20.         while (array[r] > pivot)
  21.             r -= 1;
  22.  
  23.         if (l >= r)
  24.             return r;
  25.  
  26.         tmp_ind = ind_array[l];
  27.         ind_array[l] = ind_array[r];
  28.         ind_array[r] = tmp_ind;
  29.  
  30.         tmp = array[l];
  31.         array[l] = array[r];
  32.         array[r] = tmp;
  33.         l += 1;
  34.         r -= 1;
  35.     }
  36. }
  37.  
  38. void quickSort(int* array, int* ind_array, int l, int r)
  39. {
  40.  
  41.     if (l < r) {
  42.         int q = partition(array, ind_array, l, r);
  43.         quickSort(array, ind_array, l, q);
  44.         quickSort(array, ind_array, q + 1, r);
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     int n, R, L, max_sum, min_sum, curr_sum;
  51.     int res_L, res_R;
  52.     std::cin >> n;
  53.     int a[n];
  54.     int ind_array[n];
  55.  
  56.     for (int i = 0; i < n; i++) {
  57.         std::cin >> a[i];
  58.         ind_array[i] = i + 1;
  59.     }
  60.  
  61.     quickSort(a, ind_array, 0, n - 1);
  62.  
  63.     R = 0;
  64.     max_sum = a[0];
  65.     curr_sum = a[0];
  66.  
  67.     for (L = 0; L < n; L++) {
  68.  
  69.         if (L == (n - 1)) {
  70.             min_sum = a[L];
  71.         }
  72.         else
  73.             min_sum = a[L] + a[L + 1];
  74.  
  75.         while ((R < (n - 1)) && (a[R + 1] <= min_sum)) {
  76.             R += 1;
  77.             curr_sum += a[R];
  78.         }
  79.  
  80.         if (curr_sum > max_sum) {
  81.             max_sum = curr_sum;
  82.             res_L = L;
  83.             res_R = R;
  84.         }
  85.  
  86.         curr_sum -= a[L];
  87.     }
  88.  
  89.     int len = (res_R - res_L + 1);
  90.     for (int i = 0; i < len; i++) {
  91.         a[i] = ind_array[res_L + i];
  92.     }
  93.  
  94.     quickSort(a, ind_array, 0, len - 1);
  95.  
  96.     printArray(a, 0, len - 1);
  97.  
  98.     std::cout << max_sum;
  99.  
  100.     return 0;
  101. }
RAW Paste Data