Pagini recente » Cod sursa (job #683378) | Cod sursa (job #2640299) | Cod sursa (job #1028655) | Cod sursa (job #2517694) | Cod sursa (job #59466)
Cod sursa(job #59466)
#include <assert.h>
#include <stdio.h>
enum { maxn = 500001, inf = 0x3F3F3F3F };
int n, len;
int p[maxn];
int best, best_start, best_end;
int start, end, min, minpos;
void go()
{
int i;
best = -inf;
start = 0;
end = len - 1;
while(start != n - len + 1)
{
min = inf;
for(i = start; i <= end; i++)
if(p[i] < min)
{
min = p[i];
minpos = i;
}
assert(min != inf);
//printf("start %d end %d, min %d at pos %d\n", start, end, min, minpos);
assert(end > start);
assert(end - start == len - 1);
assert(end < n);
if(min > best)
{
best = min;
best_start = start;
best_end = end;
}
start = minpos + 1;
end = start + len - 1;
}
assert(best != -inf);
//printf("final start %d end %d, best %d\n", best_start, best_end, best);
while(best-start - 1 >= 0 && p[best_start - 1] >= best)
best_start--;
//printf("brought start down to %d\n", best_start);
}
int main()
{
int i;
FILE *f = fopen("secventa.in", "r");
if(!f) return 1;
fscanf(f, "%d%d", &n, &len);
for(i = 0; i < n; i++)
fscanf(f, "%d", &p[i]);
fclose(f);
f = fopen("secventa.out", "w");
if(!f) return 1;
go();
//printf("best %d, start %d end %d\n", best, best_start, best_end);
fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best);
fclose(f);
return 0;
}