Advertisement
YEZAELP

TOI12: barrier_priority queue

Nov 4th, 2020
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None
  1. // 80/100
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. using lli = long long;
  7. const lli INF = 2e18;
  8. const int inf = 2e9;
  9. using pli = pair <lli, int>;
  10. lli qs[6000010];
  11.  
  12. int main(){
  13.  
  14.     int n, w;
  15.     scanf("%d%d", &n, &w);
  16.  
  17.     priority_queue <pli, vector <pli>, greater <pli>> pq;
  18.  
  19.     lli mx = 0;
  20.     int L = inf;
  21.     for(int i=1;i<=n;i++){
  22.  
  23.         scanf("%lld", &qs[i]);
  24.         qs[i] += qs[i-1];
  25.  
  26.         pq.push({qs[i], i});
  27.  
  28.         while(pq.size() > 0 and i - pq.top().second > w)
  29.             pq.pop();
  30.  
  31.         if(qs[i] - pq.top().first == mx){
  32.             L = min(L, i - pq.top().second);
  33.         }
  34.         else if(qs[i] - pq.top().first > mx){
  35.             mx = qs[i] - pq.top().first;
  36.             L = i - pq.top().second;
  37.         }
  38.     }
  39.  
  40.     if(L == inf) printf("0\n0");
  41.     else printf("%lld\n%d", mx, L);
  42.  
  43.     return 0;
  44. }
Advertisement
RAW Paste Data Copied
Advertisement