Pagini recente » Cod sursa (job #1184833) | Cod sursa (job #398866) | Cod sursa (job #2057736) | Cod sursa (job #1752123) | Cod sursa (job #2467637)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int v[MAXN], last[MAXN];
vector<int> dp, ans;
int n;
void scmax(){
dp.push_back(0);
for(int i = 1; i <= n; ++i){
if(v[i] > v[dp.back()]){
last[i] = dp.back();
dp.push_back(i);
continue;
}
int rez = 0, pas = 1 << 30;
while(pas){
if(rez + pas < (int)dp.size() && v[dp[rez + pas]] < v[i])
rez += pas;
pas /= 2;
}
rez++;
last[i] = dp[rez - 1];
dp[rez] = i;
}
int curent = dp.back();
while(curent){
ans.push_back(curent);
curent = last[curent];
}
reverse(ans.begin(), ans.end());
}
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i];
scmax();
fout << ans.size() << "\n";
for(auto x:ans) fout << x << " ";
return 0;
}