Advertisement
Josif_tepe

Untitled

Mar 17th, 2024
378
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6. typedef long long ll;
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(0);
  11.     cout.tie(0);
  12.  
  13.     int n,k,s;
  14.     cin>>n>>k>>s;
  15.  
  16.     vector<int> V(n);
  17.     long long z=0;
  18.     for(int i=0; i<n; i++) {
  19.         cin>>V[i];
  20.         if(i<k-1) {
  21.             z+=V[i];
  22.         }
  23.     }
  24.     int j = 0;
  25.     vector<pair<ll, int>> sums;
  26.     for(int i = k - 1; i < n; i++) {
  27.         z += V[i];
  28.         sums.push_back(make_pair(z, j));
  29.         z -= V[j];
  30.         j++;
  31.     }
  32.     sort(sums.rbegin(), sums.rend());
  33.     long long res = 0;
  34.     for(int i = 0; i < min((int) sums.size(), 3000); i++) {
  35.         ll sum = sums[i].first;
  36.         for(j = sums[i].second + s - 1; j <= sums[i].second + k - 1; j += s) {
  37.             sum -= V[j];
  38.         }
  39.         res = max(res, sum);
  40.     }
  41.     cout << res << endl;
  42.     return 0;
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement