1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 using namespace std; 5 #define max 100000+10 6 7 int a[max],sum[(max<<1)],ans; 8 int h,t,n,k; 9 deque<int> q; 10 11 void inq(int i){ 12 while(!q.empty()&&sum[i]<sum[q.back()]){ 13 q.pop_back(); 14 } 15 q.push_back(i); 16 } 17 18 void outq(){ 19 while(!q.empty()&&q.back()-q.front()>=k){ 20 q.pop_front(); 21 } 22 } 23 24 int main(){ 25 int m; 26 scanf("%d",&m); 27 while(m--){ 28 q.clear(); 29 scanf("%d%d",&n,&k); 30 sum[0]=0; 31 for(int i=1;i<=n;i++){ 32 scanf("%d",&a[i]); 33 sum[i]=sum[i-1]+a[i]; 34 } 35 for(int i=n+1;i<=n+k;i++){ 36 sum[i]=sum[i-1]+a[i-n]; 37 } 38 ans=-999999999; 39 int st,end; 40 //q[++t]=0; 41 for(int i=1;i<n+k;i++){ 42 inq(i-1); 43 outq(); 44 int res=sum[i]-sum[q.front()]; 45 if(ans<res){ 46 ans=res; 47 st=q.front()+1; 48 end=i; 49 } 50 } 51 if(st>n){ 52 st-=n; 53 } 54 if(end>n){ 55 end-=n; 56 } 57 printf("%d %d %d ",ans,st,end); 58 } 59 }