Pagini recente » Cod sursa (job #1279598) | Cod sursa (job #2321352) | Cod sursa (job #2396197) | Cod sursa (job #548837) | Cod sursa (job #27520)
Cod sursa(job #27520)
#include <stdio.h>
#include <string.h>
#define filein "secventa.in"
#define fileout "secventa.out"
#define NMax 5000
#define NMaxS 3800
typedef char string[NMaxS + 10];
typedef struct {
int poz;
int V;
}entry ;
int n, k;
string S;
int v[NMax + 1];
entry Q[NMax + 1];
int MAX, prim;
void citire()
{
FILE *fin = fopen(filein, "r");
int i, nr = 0, x = 0, len, sign = 1, ok = 0;
fscanf(fin, "%d %d", &n, &k);
fgets(S, 10, fin);
fgets(S, NMaxS, fin);
len = strlen(S);
for (i = 0; i < len; i++)
if (S[i] == '-')
sign = -1;
else if (S[i] >= '0' && S[i] <= '9')
{
x = x * 10 + (S[i] - '0');
ok = 1;
}
else if (ok)
{
v[++nr] = x * sign;
x = 0; sign = 1;
ok = 0;
}
if (ok)
v[++nr] = x * sign;
fclose(fin);
}
void compute()
{ int i, last = 1, first = 1;
MAX = -30001;
Q[1].poz = 1; Q[1].V = v[1];
for (i = 2; i <= n; i++)
{
while (first <= last && Q[first].poz <= i-k) first++;
while (last >= first && Q[last].V >= v[i]) last--;
Q[++last].poz = i;
Q[last].V = v[i];
if (i >= k)
{
if (Q[first].V > MAX)
{ MAX = Q[first].V; prim = i; }
}
}
}
void print()
{
FILE *fout = fopen(fileout, "w");
fprintf(fout, "%d %d %d\n", prim-k+1, prim, MAX);
fclose(fout);
}
FILE *fout,*fin;
int i, nr = 0, x = 0, len, sign = 1, ok = 0;
int last = 1, first = 1;
int main()
{
// citire();
fout = fopen(fileout, "w");
fin = fopen(filein, "r");
fscanf(fin, "%d %d", &n, &k);
fgets(S, 10, fin);
fgets(S, NMaxS, fin);
len = strlen(S);
for (i = 0; i < len; i++)
if (S[i] == '-')
sign = -1;
else if (S[i] >= '0' && S[i] <= '9')
{
x = x * 10 + (S[i] - '0');
ok = 1;
}
else if (ok)
{
v[++nr] = x * sign;
x = 0; sign = 1;
ok = 0;
}
if (ok)
v[++nr] = x * sign;
fclose(fin);
// compute();
MAX = -30001;
Q[1].poz = 1; Q[1].V = v[1];
for (i = 2; i <= n; i++)
{
while (first <= last && Q[first].poz <= i-k) first++;
while (last >= first && Q[last].V >= v[i]) last--;
Q[++last].poz = i;
Q[last].V = v[i];
if (i >= k)
{
if (Q[first].V > MAX)
{ MAX = Q[first].V; prim = i; }
}
}
// print();
fprintf(fout, "%d %d %d\n", prim-k+1, prim, MAX);
fclose(fout);
return 0;
}