Advertisement
Josif_tepe

Untitled

Mar 21st, 2025
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 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 pref_sum[maxn];
  9. int n, l;
  10. int query(int i, int j) {
  11.     if(i == 0) {
  12.         return pref_sum[j];
  13.     }
  14.     return pref_sum[j] - pref_sum[i - 1];
  15. }
  16. bool check(int frogs) {
  17.     for(int i = 0; i < n; i++) {
  18.         if(i + l - 1 >= n) {
  19.             return true;
  20.         }
  21.        
  22.         if(query(i, i + l - 1) < frogs) {
  23.             return false;
  24.         }
  25.     }
  26.     return true;
  27. }
  28.  
  29. int main() {
  30.    
  31.     cin >> n;
  32.     cin >> l;
  33.     n--;
  34.     vector<int> v(n);
  35.    
  36.     int sum = 0;
  37.     for(int i = 0; i < n; i++) {
  38.         cin >> v[i];
  39.         sum += v[i];
  40.        
  41.         pref_sum[i] = sum;
  42.     }
  43.    
  44.     int L = 0, R = 1e9;
  45.     int res = 0;
  46.     while(L <= R) {
  47.         int mid = (L + R) / 2;
  48.        
  49.         if(check(mid)) {
  50.             res = mid;
  51.             L = mid + 1;
  52.         }
  53.         else {
  54.             R = mid - 1;
  55.         }
  56.     }
  57.    
  58.     cout << res << endl;
  59.     return 0;
  60. }
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement