YEZAELP

PROG-1108 : สายแร่แห่งพลัง 2 (ore2) (Deque)

Dec 2nd, 2021
635
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. using pli = pair <lli, int>;
  6. const int N = 1e6 + 10;
  7. lli qs[N], dp[N];
  8.  
  9. int main(){
  10.  
  11.     int n, k;
  12.     scanf("%d %d", &n, &k);
  13.  
  14.     for(int i=1;i<=n;i++){
  15.         scanf("%lld", &qs[i]);
  16.         qs[i] += qs[i - 1];
  17.     }
  18.  
  19.     deque <pli> dq; /// (-qs[i] + dp[i - 1], i)
  20.     dq.push_back({0, 0});
  21.     dp[1] = qs[1] > k ? 0: qs[1];
  22.  
  23.     for(int i=2;i<=n;i++){
  24.         lli cur = -qs[i - 1] + dp[i - 2];
  25.         while(!dq.empty() and cur >= dq.back().first)
  26.             dq.pop_back();
  27.         dq.push_back({cur, i - 1});
  28.  
  29.         while(!dq.empty() and qs[i] - qs[dq.front().second] > k)
  30.             dq.pop_front();
  31.  
  32.         if(dq.size() == 0) dp[i] = dp[i - 1];
  33.         else dp[i] = max(dp[i - 1], qs[i] + dq.front().first);
  34.     }
  35.  
  36.     printf("%lld", dp[n]);
  37.  
  38.     return 0;
  39. }
RAW Paste Data