Advertisement
Josif_tepe

Untitled

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