Advertisement
YEZAELP

TOI12: barrier_deque

Nov 4th, 2020
127
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.  
  5. using lli = long long;
  6. const lli INF = 2e18;
  7. const int inf = 2e9;
  8. using pli = pair <lli, int>;
  9. lli qs[6000010];
  10.  
  11. int main(){
  12.  
  13.     int n, w;
  14.     scanf("%d%d", &n, &w);
  15.  
  16.     deque <pli> dq;
  17.  
  18.     lli mx = 0;
  19.     int L = inf;
  20.     for(int i=1;i<=n;i++){
  21.  
  22.         scanf("%lld", &qs[i]);
  23.         qs[i] += qs[i-1];
  24.  
  25.         while(dq.size() > 0 and qs[i-1] - dq.back().first <= 0) // ช่วงนั้นๆเป็น - หรือ 0 ไม่ควรนำมารวมด้วย
  26.             dq.pop_back();
  27.  
  28.         dq.push_back({qs[i-1], i});
  29.  
  30.         while(dq.size() > 0 and i - dq.front().second + 1 > w) // ไม่อยู่ในช่วงที่จะพิจารณา
  31.             dq.pop_front();
  32.  
  33.         if(qs[i] - dq.front().first == mx){ // ผลรวมเท่ากันเอาความยาวที่สั้นที่สุด
  34.             L = min(L, i - dq.front().second + 1);
  35.         }
  36.         else if(qs[i] - dq.front().first > mx){
  37.             mx = qs[i] - dq.front().first; // หาผลรวมที่มากที่สุด
  38.             L = i - dq.front().second + 1; // ความยาว
  39.         }
  40.     }
  41.  
  42.     if(mx <= 0) printf("0\n0");
  43.     else printf("%lld\n%d", mx, L);
  44.  
  45.     return 0;
  46. }
Advertisement
RAW Paste Data Copied
Advertisement