Mai intai trebuie sa te autentifici.
Cod sursa(job #203746)
Utilizator | Data | 19 august 2008 11:45:53 | |
---|---|---|---|
Problema | Subsir 2 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.04 kb |
#include <cstdio>
#define min(x,y) x<y ? x:y
#define IN "subsir2.in"
#define OUT "subsir2.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<13
int N;
short int A[N_MAX],T[N_MAX];
int V[N_MAX];
void scan()
{
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%d\n", &N);
FOR(i,1,N) scanf("%d", &V[i]);
}
void solve()
{
int best(0),minim(1<<21);
A[0] = 1<<13;
V[0] = 1<<21;
for(int i=N;i>=1;--i)
{
FOR(j,i+1,N)
if(V[j] >= V[i])
{
if(V[j] < minim && (A[j] < A[best] || (A[j] == A[best] && V[j] < V[best])) )
best = j;
minim = min(minim,V[j]);
}
if(best)
A[i] = A[best] + 1,
T[i] = best;
else
A[i] = 1;
best = 0;
minim = 1<<21;
}
FOR(i,1,N)
{
if(V[i] < minim && (A[i] < A[best] || (A[i] == A[best] && V[i] < V[best])))
best = i;
minim = min(minim,V[i]);
}
printf("%d\n", A[best]);
int rez = best;
FOR(i,1,A[rez])
{
printf("%d ",best);
best = T[best];
}
}
int main()
{
scan();
solve();
return 0;
}