【HDU】3415 Max Sum of MaxKsubsequence

 1 #include<cstdio>
 2 #define INF 123456789
 3 #define MAXN 200010
 4 int a[MAXN],q[MAXN];
 5 int main()
 6 {
 7     int c,n,m,k,i,j;
 8     int front,rear;
 9     int ans,st,en;
10     scanf("%d",&c);
11     while(c--)
12     {
13         ans=-INF;
14         front=0;
15         rear=-1;
16         scanf("%d%d",&n,&k);
17         for(m=n,a[0]=0,i=1;i<=n;i++)
18         {
19             scanf("%d",&a[i]);
20             a[i+n]=a[i];
21         }
22         for(n+=k,i=1;i<=n;i++)
23             a[i]+=a[i-1];
24         for(i=1;i<=n;i++)
25         {
26             for(;front<=rear&&q[front]<i-k;front++);
27             for(;front<=rear&&a[i-1]<=a[q[rear]];rear--);
28             q[++rear]=i-1;
29             if(ans<a[i]-a[q[front]])
30             {
31                 ans=a[i]-a[q[front]];
32                 st=q[front]+1;
33                 en=i;
34             }
35         }
36         if(en>m)
37             en-=m;
38         printf("%d %d %d\n",ans,st,en);
39     }
40     return 0;
41 }