josiftepe

Untitled

Oct 24th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. #include <set>
  6. using namespace std;
  7. typedef long long ll;
  8. vector<ll> v, pref_sum;
  9. ll sum(int L, int R) {
  10.     if(L - 1 < 0) {
  11.         return pref_sum[R];
  12.     }
  13.     return pref_sum[R] - pref_sum[L - 1];
  14. }
  15. int main() {
  16.     ios_base::sync_with_stdio(false);
  17.     int n;
  18.     cin >> n;
  19.     ll M;
  20.     cin >> M;
  21.     ll s = 0;
  22.     for(int i =0 ; i < n; ++i) {
  23.         ll x;
  24.         cin >> x;
  25.         v.push_back(x);
  26.         s += x;
  27.         pref_sum.push_back(s);
  28.     }
  29.     int ret = 0;
  30.     for(int i = 0; i < n; ++i) {
  31.         int L = i + 1;
  32.         int R = n - 1;
  33.         while(L <= R) {
  34.             int mid = (L + R) / 2;
  35.             if(sum(i, mid) <= M) {
  36.                 ret = max(ret, mid - i + 1);
  37.                 L = mid + 1;
  38.             }
  39.             else {
  40.                 R = mid - 1;
  41.             }
  42.         }
  43.     }
  44.     cout << ret << endl;
  45.     return 0;
  46. }
  47.  
  48.  
  49.  
  50.  
  51.  
  52. /*
  53.  8
  54.  1 2 1 3 2 7 4 2 1 2 3 4 5 6 7 8
  55.  */
  56.  
Advertisement
Add Comment
Please, Sign In to add comment