Advertisement
SuitNdtie

Barrier2

May 30th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<queue>
  3. #include<deque>
  4. using namespace std;
  5. typedef long long int ll;
  6. int n,w;
  7. int const N = 6000010;
  8. ll arr[N];
  9. ll qs[N];
  10.  
  11. ll max(ll a,ll b){
  12.     return a > b ? a : b;
  13. }
  14. ll min(ll a,ll b){
  15.     return a < b ? a : b;
  16. }
  17.  
  18. ll dp[N];
  19.  
  20. int main()
  21. {
  22.     scanf("%d %d",&n,&w);
  23.     for(int i = 1 ; i <= n ; i ++){
  24.         scanf("%lld",&arr[i]);
  25.         qs[i] = qs[i-1] + arr[i];
  26.     }
  27.     priority_queue<pair<ll , int > , vector<pair<ll,int > > , greater<pair<ll,int> > > pq;
  28.     deque<pair<ll, int > > dq;
  29.     pq.push({0,0});
  30.    
  31.     ll ansmax = 0;
  32.     ll anslen = 0;
  33.     for(int i = 1 ; i <= n ; i ++){
  34.         ll nv = qs[i-1];
  35.     //  pq.push({qs[i-1],i-1});
  36.         while(!dq.empty() && dq.back().first > nv)dq.pop_back();
  37.        
  38.         dq.push_back({nv,i-1});
  39.        
  40.         while(!dq.empty() && i - dq.front().second > w)dq.pop_front();
  41.            
  42.         if(qs[i] - dq.front().first > ansmax){
  43.             ansmax = qs[i] - dq.front().first;
  44.             anslen = i - dq.front().second;
  45.         }
  46.         else if(qs[i] - dq.front().first == ansmax){
  47.             anslen = min(anslen , i - dq.front().second);
  48.         }
  49.     }
  50.     printf("%lld\n%lld",ansmax,anslen);
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement