Advertisement
YEZAELP

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

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