Pagini recente » Cod sursa (job #381234) | Cod sursa (job #26470) | Cod sursa (job #886817) | Cod sursa (job #1137683) | Cod sursa (job #809986)
Cod sursa(job #809986)
#include<stdio.h>
#include<string.h>
#define Nmax 500001
#define INF 0x3f3f3f
#define BUF_SIZE 7*Nmax
int N,K,v[Nmax],d[2][Nmax];
char buf[BUF_SIZE];
int main()
{
FILE*f = fopen("secventa.in","r");
fscanf(f,"%d%d",&N,&K);
fgets(buf, BUF_SIZE, f);
fgets(buf, BUF_SIZE, f);
int size = strlen(buf),i,cnt,negative=0;
for(i=1,cnt=0;cnt<size;++cnt)
{
if(buf[cnt] == 32 || buf[cnt] =='\n')
{
if(negative)
v[i] *= -1;
++i;
negative = 0;
continue;
}
if(buf[cnt] == '-')
{
negative = 1;
continue;
}
v[i] = v[i]*10 + (buf[cnt]-'0');
}
int st=1,fn=0,better,sol=-INF,sol_left,sol_right;//d[1][i] valoarea, d[0][i] pozitia de inceput a secv
for(i=1;i<=N;++i)
{
better = 0;
while(fn>=st && v[i] <= d[1][fn])
{
--fn;
better = 1;
}
++fn;
if(better == 0)
{
d[0][fn] = i;
}
d[1][fn] = v[i];
if(st<fn && i - d[0][st+1] + 1 >= K)
++st;
if(i - d[0][st] + 1 >= K)
{
if(d[1][st] > sol)
{
sol = d[1][st];
sol_left = d[0][st];
sol_right = i;
}
}
}
FILE*g = fopen("secventa.out","w");
fprintf(g,"%d %d %d\n", sol_left, sol_right, sol);
fclose(g);
return 0;
}