Advertisement
Josif_tepe

Untitled

Mar 21st, 2025
371
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 1e5 + 100;
  8. int n, l;
  9. int a[maxn];
  10. ll pref[maxn];
  11.  
  12. ll query(int i, int j) {
  13.     if(i == 0) {
  14.         return pref[j];
  15.     }
  16.     return pref[j] - pref[i - 1];
  17. }
  18.  
  19. bool check(ll frogs) {
  20.     for(int i = 0; i < n; i++) {
  21.         if(i + l - 1 >= n) {
  22.             return true;
  23.         }
  24.         if(query(i, i + l - 1) < frogs) {
  25.             return false;
  26.         }
  27.        
  28.     }
  29.     return true;
  30. }
  31. int main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin >> n >> l;
  34.    
  35.     n--;
  36.     ll sum = 0;
  37.     for(int i = 0; i < n; i++) {
  38.         cin >> a[i];
  39.        
  40.         sum += a[i];
  41.         pref[i] = sum;
  42.     }
  43.    
  44.     ll L = 0, R = 2e9;
  45.     ll res= 0 ;
  46.     while(L <= R) {
  47.         ll mid = (L + R) / 2;
  48.        
  49.         if(check(mid)) {
  50.             res = max(res, mid);
  51.             L = mid + 1;
  52.         }
  53.         else {
  54.             R = mid - 1;
  55.         }
  56.     }
  57.     cout << res << endl;
  58.     return 0;
  59. }
  60.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement