Advertisement
Josif_tepe

Untitled

Apr 12th, 2021
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. int a[100005];
  4. int n;
  5. int pref_sum[100005];
  6. int sum(int i, int j) {
  7.     if(i == 0) {
  8.         return pref_sum[j];
  9.     }
  10.     return pref_sum[j] - pref_sum[i - 1];
  11. }
  12. int main() {
  13.     int m;
  14.     cin >> n >> m;
  15.     int s = 0;
  16.     for(int i = 0; i < n; i++) {
  17.         cin >> a[i];
  18.         s += a[i];
  19.         pref_sum[i] = s;
  20.     }
  21.     int ret = 0;
  22.     for(int i = 0; i < n; i++) { // probuvame da pocneme od sekoja pozicija
  23.         int L = i + 1;
  24.         int R = n - 1;
  25.         while(L <= R) {
  26.             int middle = (L + R) / 2;
  27.             if(sum(i, middle) <= m) {
  28.                 ret = max(ret, middle - i + 1);
  29.                 L = middle + 1;
  30.             }
  31.             else {
  32.                 R = middle - 1;
  33.             }
  34.         }
  35.     }
  36.     cout << ret << endl;
  37.     return 0;
  38. }
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement