Advertisement
Josif_tepe

Untitled

Apr 12th, 2021
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. int a[200005];
  4. int pref_sum[200005];
  5. int sum(int i, int j) {
  6.     if(i == 0) {
  7.         return pref_sum[j];
  8.     }
  9.     return pref_sum[j] - pref_sum[i - 1];
  10. }
  11. int main() {
  12.     int n, k;
  13.     cin >> n >> k;
  14.     int s = 0;
  15.     for(int i = 0; i < n; i++) {
  16.         cin >> a[i];
  17.         a[i] = 1 - a[i];
  18.         s += a[i];
  19.         pref_sum[i] = s;
  20.     }
  21.     int ret = 0, si, ei;
  22.     for(int i = 0; i < n; i++) {
  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) <= k) {
  28.                 if(ret < middle - i + 1) {
  29.                     ret = middle - i + 1;
  30.                     si = i;
  31.                     ei = middle;
  32.                 }
  33.                 L = middle + 1;
  34.             }
  35.             else {
  36.                 R = middle - 1;
  37.             }
  38.         }
  39.     }
  40.     cout << ret << endl;
  41.     for(int i = si; i <= ei; i++) {
  42.         if(a[i] == 1) {
  43.             cout << i + 1 << " ";
  44.         }
  45.     }
  46.     return 0;
  47. }
  48. // 1 2 3 4 5
  49. // a --> b imame tocno b - a + 1
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement