YEZAELP

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

Jul 19th, 2020 (edited)
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using lli = long long;
  5. using pli = pair<lli,int>;
  6. lli dp[1000001],qs[1000001];
  7. int n,k;
  8.  
  9. int main(){
  10.  
  11.     scanf("%d%d",&n,&k);
  12.  
  13.     for(int i=1;i<=n;i++){
  14.         scanf("%lld",&qs[i]);
  15.         qs[i] += qs[i-1];
  16.     }
  17.  
  18.     priority_queue <pli> pq;
  19.  
  20.     for(int i=1;i<=n;i++){
  21.  
  22.         if(i == 1) pq.push({0,1});
  23.         else pq.push({dp[i-2]-qs[i-1],i});
  24.  
  25.         while(pq.size() > 0 and qs[i] - qs[pq.top().second-1] > k){
  26.             pq.pop();
  27.         }
  28.  
  29.         if(pq.size() == 0) dp[i] = dp[i-1];
  30.         else dp[i] = max(dp[i-1],qs[i]+pq.top().first);
  31.     }
  32.  
  33.     printf("%lld",dp[n]);
  34.  
  35.     return 0;
  36. }
RAW Paste Data Copied