Cod sursa(job #2609501)

Utilizator juniorOvidiu Rosca junior Data 2 mai 2020 19:32:44
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct element {
  int v, l; // valoarea, locul
};

ifstream fin("scmax.in");
ofstream fout("scmax.out");
vector<element> sv[10001];
int n, a, nv, ne[10001], s[10001], lp, vp, iv;
bool gasit;

int main() {
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> a;
    gasit = false;
    for (int isv = 1; isv <= nv and not gasit; isv++)
      if (a <= sv[isv][ne[isv]].v) { // <
        sv[isv].push_back({a, i});
        ne[isv]++;
        gasit = true;
      }
    if (not gasit) {
      nv++; sv[nv].push_back({a, i});
    }
  }
  fout << nv << '\n';
  s[nv] = sv[nv][0].v; lp = sv[nv][0].l; vp = s[nv];
  for (int isv = nv - 1; isv >= 1; isv--) {
    for (iv = 0; (sv[isv][iv].v >= vp) or (sv[isv][iv].l > lp); iv++);
    s[isv] = sv[isv][iv].v; lp = sv[isv][iv].l; vp = s[isv];
  }
  for (int is = 1; is <= nv; is++)
    fout << s[is] << ' ';
}