fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #ifndef fruit_loving_dinosaur
  4. #define endl '\n'
  5. #endif
  6. #define problem ""
  7. #define multitest 0
  8. #define debug(x) cerr << #x << " = " << x << endl;
  9. void init()
  10. {
  11. }
  12. int dq[100000];
  13. void eat()
  14. {
  15.     int n, q;
  16.     cin >> n >> q;
  17.     vector<int> v(n);
  18.     for (auto &i : v)
  19.         cin >> i;
  20.     while (q--)
  21.     {
  22.         int start = 0, size = 0;
  23.         int S;
  24.         cin >> S;
  25.         int cost = 0;
  26.         int l = 0;
  27.         int X = 0;
  28.         for (int i = 0; i < n; i++)
  29.         {
  30.             while (size && v[dq[start + size - 1]] < v[i])
  31.                 size--;
  32.             dq[start + (size++)] = i;
  33.             cost += v[i];
  34.             while (size && cost - (v[dq[start]] / 2) - (v[dq[start]] % 2) > S)
  35.             {
  36.                 while (size && dq[start] <= l)
  37.                     start++, size--;
  38.                 cost -= v[l++];
  39.             }
  40.             X = max(X, i - l + 1);
  41.         }
  42.         cout << X << endl;
  43.     }
  44. }
  45. signed main()
  46. {
  47. #ifndef fruit_loving_dinosaur
  48.     ios::sync_with_stdio(0);
  49.     cin.tie(0);
  50.     cout.tie(0);
  51.     if (fopen(problem ".inp", "r"))
  52.     {
  53.         freopen(problem ".inp", "r", stdin);
  54.         freopen(problem ".out", "w", stdout);
  55.     }
  56. #endif
  57.     init();
  58.     int t = 1;
  59. #if multitest
  60.     cin >> t;
  61. #endif
  62.     while (t--)
  63.         eat();
  64. }
  65.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
12 6
4 9 5 4 8 4 5 4 8 6 9 7
26
39
100
10
2
1
stdout
copy 
6
8
12
3
1
0
https://ideone.com/5rWWgh
language:
C++14 (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!