Pagini recente » Cod sursa (job #1325197) | Cod sursa (job #2571430) | Cod sursa (job #2231114) | Cod sursa (job #2232242) | Cod sursa (job #68401)
Cod sursa(job #68401)
//using namespace std;
#define MAX_N 50005
#include <stdio.h>
FILE *fin=fopen("secv2.in","r"),
*fout=fopen("secv2.out","w");
int b[MAX_N];
int deq[MAX_N];
int i,lf,li,in,out,max;
int n,k,x;
void arrange(int p)
{
while (p>0 && b[deq[p]]<b[deq[p-1]])
{ deq[p-1]=deq[p]; p--; }
}
int main()
{
fscanf(fin,"%d %d",&n,&k);
for (i=1; i<=n; i++) {
fscanf(fin,"%d",&x);
b[i]=b[i-1]+x;
}
li=0; lf=1;
max=-1000000;
if (k==n)
{
fprintf(fout,"1 %d %d",n,b[n]);
return 0;
}
for (i=1; i<=n; i++)
{
deq[lf++]=i;
if (i-k>0) arrange(i-k+1);
if (i-deq[li]>=k)
if (b[i]-b[deq[li]]>max)
{
max=b[i]-b[deq[li]];
in=deq[li]+1;
out=i;
}
}
fprintf(fout,"%d %d %d",in,out,max);
fclose(fin);
fclose(fout);
return 0;
}