Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<queue>
- #include<deque>
- using namespace std;
- typedef long long int ll;
- int n,w;
- int const N = 6000010;
- ll arr[N];
- ll qs[N];
- ll max(ll a,ll b){
- return a > b ? a : b;
- }
- ll min(ll a,ll b){
- return a < b ? a : b;
- }
- ll dp[N];
- int main()
- {
- scanf("%d %d",&n,&w);
- for(int i = 1 ; i <= n ; i ++){
- scanf("%lld",&arr[i]);
- qs[i] = qs[i-1] + arr[i];
- }
- priority_queue<pair<ll , int > , vector<pair<ll,int > > , greater<pair<ll,int> > > pq;
- deque<pair<ll, int > > dq;
- pq.push({0,0});
- ll ansmax = 0;
- ll anslen = 0;
- for(int i = 1 ; i <= n ; i ++){
- ll nv = qs[i-1];
- // pq.push({qs[i-1],i-1});
- while(!dq.empty() && dq.back().first > nv)dq.pop_back();
- dq.push_back({nv,i-1});
- while(!dq.empty() && i - dq.front().second > w)dq.pop_front();
- if(qs[i] - dq.front().first > ansmax){
- ansmax = qs[i] - dq.front().first;
- anslen = i - dq.front().second;
- }
- else if(qs[i] - dq.front().first == ansmax){
- anslen = min(anslen , i - dq.front().second);
- }
- }
- printf("%lld\n%lld",ansmax,anslen);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement