fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. int main() {
  11.     ios_base::sync_with_stdio(false);
  12.     cin.tie(NULL);
  13.  
  14.     int n, d;
  15.     ll p;
  16.     if (!(cin >> n >> p >> d)) return 0;
  17.  
  18.     vector<ll> w(n);
  19.     vector<ll> pref(n + 1, 0);
  20.     for (int i = 0; i < n; ++i) {
  21.         cin >> w[i];
  22.         pref[i + 1] = pref[i] + w[i];
  23.     }
  24.  
  25.     auto get_sum = [&](int l, int r) {
  26.         if (l > r) return 0LL;
  27.         return pref[r + 1] - pref[l];
  28.     };
  29.  
  30.     auto get_cost = [&](int l, int r, ll max_decha_sum) {
  31.         return get_sum(l, r) - max_decha_sum;
  32.     };
  33.  
  34.     deque<int> dq;
  35.     int left = 0;
  36.     int max_len = 0;
  37.  
  38.     for (int right = 0; right < n; ++right) {
  39.         int decha_start = right - d + 1;
  40.         if (decha_start >= 0) {
  41.             ll current_decha_sum = get_sum(decha_start, right);
  42.             while (!dq.empty() && get_sum(dq.back(), dq.back() + d - 1) <= current_decha_sum) {
  43.                 dq.pop_back();
  44.             }
  45.             dq.push_back(decha_start);
  46.         }
  47.  
  48.         while (!dq.empty() && dq.front() < left) {
  49.             dq.pop_front();
  50.         }
  51.  
  52.         while (left <= right) {
  53.             ll best_decha = 0;
  54.             if (!dq.empty()) {
  55.                 best_decha = get_sum(dq.front(), dq.front() + d - 1);
  56.             }
  57.  
  58.             if (right - left + 1 <= d) {
  59.                 if (get_sum(left, right) - get_sum(left, right) <= p) break;
  60.             } else {
  61.                 if (get_cost(left, right, best_decha) <= p) break;
  62.             }
  63.  
  64.             left++;
  65.             while (!dq.empty() && dq.front() < left) {
  66.                 dq.pop_front();
  67.             }
  68.         }
  69.         max_len = max(max_len, right - left + 1);
  70.     }
  71.  
  72.     cout << max_len << endl;
  73.  
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
9 7 2
3 4 1 9 4 1 7 1 3
stdout
copy 
5
https://ideone.com/eyJuPO
language:
C++14 (gcc 8.3)
created:
2 days 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!