# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
963798 | Kakarot | Global Warming (CEOI18_glo) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>#define int int64_tusing namespace std;void setIO() { cin.tie(0)->sync_with_stdio(0);}int lis(vector<int> &a, int i, int j) { vector<int> seq; for(int k = i; k < j+1; k++) { auto it = lower_bound(seq.begin(), seq.end(), a[k]); if(it == seq.end()) seq.push_back(a[k]); else *it = a[k]; } return seq.size();}void solve() { int n, x, ans = 0; cin >> n >> x; vector<int> a(n); for(auto &e : a) cin >> e; if(x == 0) { cout << lis(a, 0, n-1); return; } vector<int> plis(n), slis(n); for(int i = 0; i < n; i++) plis[i] = lis(a, 0, i); for(int i = n-1; i > -1; i--) slis[i] = lis(a, i, n-1); for(int i = 0; i < n-1; i++) ans = max(ans, plis[i] + slis[i+1]); cout << ans;}int32_t main() { setIO(); solve(); return 0;}