Pagini recente » Cod sursa (job #1596437) | Cod sursa (job #2496339) | Cod sursa (job #2867733) | Cod sursa (job #2439805) | Cod sursa (job #56988)
Cod sursa(job #56988)
#include<stdio.h>
#define MAXN 1000001
#define INF 1000000000
int pA,pB,REZ,N,U,L,V[MAXN],deque[MAXN];
int poz[MAXN],X[MAXN],query[MAXN];
void citesteDate(){
int i;
freopen("secv2.in","r",stdin);
scanf("%d %d",&N,&L);
U=N;
for(i=1;i<=N;i++) scanf("%d ",&V[i]);
}
void proceseaza(){
int i,j,s1,s2;
for (s1=1,s2=1,i=1;i<=N;i++){
X[i]=X[i-1]+V[i];
while (s1<=s2 && deque[s2]>X[i])s2--;
s2++;
deque[s2]=X[i];
poz[s2]=i;
while (s1<=s2 && poz[s1]+U-L<i) s1++;
query[i]=poz[s1];
}
REZ=-INF;
for (i=L;i<=N;i++){
j=query[i-L];
if (X[i]-X[j]>REZ){
REZ=X[i]-X[j];pA=j+1;pB=i;
}
}
}
void afiseazaRez(){
freopen("secv2.out","w",stdout);
printf("%d %d %d\n",pA,pB,REZ);
}
int main()
{
citesteDate();
proceseaza();
afiseazaRez();
return 0;
}