Advertisement
YEZAELP

PROG-1157: ส่งกระแสไฟฟ้า (electricity)_deque

Nov 4th, 2020 (edited)
126
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. const int N = 500010;
  7. using pli = pair <lli, int>;
  8.  
  9. int main(){
  10.  
  11.     int n, k;
  12.     scanf("%d%d", &n, &k);
  13.  
  14.     deque <pli> dq;
  15.  
  16.     lli ans = 0;
  17.     for(int i=1;i<=n;i++){
  18.         lli x;
  19.         scanf("%lld", &x);
  20.  
  21.         while(dq.size() > 0 and i - dq.front().second > k) dq.pop_front();
  22.  
  23.         if(i == 1) ans = x;
  24.         else ans = x + dq.front().first;
  25.  
  26.         while(dq.size() > 0 and dq.back().first >= ans) dq.pop_back(); // ต้องหารค่าที่น้อยที่สุด จึงลบค่าที่มากกว่าทิ้งไป
  27.  
  28.         dq.push_back({ans, i});
  29.     }
  30.     printf("%lld", ans);
  31.  
  32.     return 0;
  33. }
Advertisement
RAW Paste Data Copied
Advertisement