Submission #64338
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | #include "bits/stdc++.h" // Begin Header {{{ #pragma region using namespace std; using usize = size_t ; using imax = intmax_t; #ifndef DEBUG #define dump(...) #endif #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) #define let const auto constexpr size_t operator "" _zu(unsigned long long value) { return value; }; constexpr intmax_t operator "" _jd(unsigned long long value) { return value; }; constexpr uintmax_t operator "" _ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template < class T, class Compare = less<>> using MaxHeap = priority_queue<T, vector<T>, Compare>; template < class T, class Compare = greater<>> using MinHeap = priority_queue<T, vector<T>, Compare>; inline void input() {} template < class Head, class ... Tail> inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward<Tail>(tail)...); } template < class Container, class Value = typename Container::value_type, enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr> inline istream& operator>>(istream &is, Container &vs) { for (auto &v: vs) is >> v; return is; } inline void output() { cout << "\n" ; } template < class Head, class ... Tail> inline void output(Head&& head, Tail&&... tail) { cout << head; if ( sizeof ...(tail)) cout << " " ; output(forward<Tail>(tail)...); } template < class Container, class Value = typename Container::value_type, enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr> inline ostream& operator<<(ostream &os, const Container &vs) { static constexpr const char *delim[] = { " " , "" }; for (auto it = begin(vs); it != end(vs); ++it) { os << delim[it == begin(vs)] << *it; } return os; } template < class Iterator> inline void join( const Iterator &Begin, const Iterator &End, const string &delim = "\n" , const string &last = "\n" ) { for (auto it = Begin; it != End; ++it) { cout << ((it == Begin) ? "" : delim) << *it; } cout << last; } template < class T> inline vector<T> makeVector( const T &init_value, size_t sz) { return vector<T>(sz, init_value); } template < class T, class ... Args> inline auto makeVector( const T &init_value, size_t sz, Args... args) { return vector<decltype(makeVector<T>(init_value, args...))>(sz, makeVector<T>(init_value, args...)); } template < class Func> class FixPoint : Func { public : explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {} template < class ... Args> constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(* this , std::forward<Args>(args)...); } }; template < class Func> static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint<Func>{forward<Func>(f)}; } template < class Container> struct reverse_t { Container &c; reverse_t(Container &c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template < class Container> auto reversed(Container &c) { return reverse_t<Container>(c); } template < class T> inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true ); } template < class T> inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true ); } template < class T> inline T diff( const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } void ioinit() { ios_base::sync_with_stdio( false ); cin.tie(nullptr); cout << fixed << setprecision(10); clog << fixed << setprecision(10); } #pragma endregion // }}} End Header signed main() { ioinit(); var(usize, N); vector<imax> a(N); input(a); vector<imax> lis_arr(N, INF), lis_len(N); vector<imax> lis_rev_arr(N, INF), lis_rev_len(N); rep(i, 0, N) { *lower_bound(all(lis_arr), a[i]) = a[i]; lis_len[i] = distance(lis_arr.begin(), lower_bound(all(lis_arr), INF)); } repr(i, N - 1, 0) { *lower_bound(all(lis_rev_arr), a[i]) = a[i]; lis_rev_len[i] = distance(lis_rev_arr.begin(), lower_bound(all(lis_rev_arr), INF)); } imax res = 0; rep(i, 0, N - 1) { chmax(res, lis_len[i] + lis_rev_len[i] - 1); } chmax(res, lis_len[N - 1]); output(res); return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 1418 - 山形数列 |
ユーザー名 | もけ |
投稿日時 | 2020-10-17 16:39:19 |
言語 | C++17 |
状態 | Accepted |
得点 | 1 |
ソースコード長 | 4811 Byte |
最大実行時間 | 63 ms |
最大メモリ使用量 | 8552 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 1 / 1 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in01.txt | AC | 42 ms | 4188 KB |
1
|
in02.txt | AC | 24 ms | 812 KB |
1
|
in03.txt | AC | 51 ms | 6532 KB |
1
|
in04.txt | AC | 59 ms | 8388 KB |
1
|
in05.txt | AC | 60 ms | 8332 KB |
1
|
in06.txt | AC | 57 ms | 8400 KB |
1
|
in07.txt | AC | 59 ms | 8340 KB |
1
|
in08.txt | AC | 53 ms | 8280 KB |
1
|
in09.txt | AC | 59 ms | 8468 KB |
1
|
in10.txt | AC | 62 ms | 8412 KB |
1
|
in11.txt | AC | 53 ms | 8484 KB |
1
|
in12.txt | AC | 63 ms | 8296 KB |
1
|
in13.txt | AC | 62 ms | 8492 KB |
1
|
in14.txt | AC | 58 ms | 8428 KB |
1
|
in15.txt | AC | 61 ms | 8496 KB |
1
|
in16.txt | AC | 61 ms | 8440 KB |
1
|
in17.txt | AC | 57 ms | 8384 KB |
1
|
in18.txt | AC | 63 ms | 8456 KB |
1
|
in19.txt | AC | 61 ms | 8404 KB |
1
|
in20.txt | AC | 52 ms | 8472 KB |
1
|
in21.txt | AC | 50 ms | 8536 KB |
1
|
in22.txt | AC | 55 ms | 8476 KB |
1
|
in23.txt | AC | 51 ms | 8544 KB |
1
|
in24.txt | AC | 45 ms | 8360 KB |
1
|
in25.txt | AC | 49 ms | 8428 KB |
1
|
in26.txt | AC | 51 ms | 8500 KB |
1
|
in27.txt | AC | 17 ms | 632 KB |
1
|
in28.txt | AC | 16 ms | 588 KB |
1
|
in29.txt | AC | 17 ms | 544 KB |
1
|
in30.txt | AC | 17 ms | 504 KB |
1
|
in31.txt | AC | 16 ms | 720 KB |
1
|
in32.txt | AC | 19 ms | 676 KB |
1
|
in33.txt | AC | 15 ms | 636 KB |
1
|
in34.txt | AC | 21 ms | 592 KB |
1
|
in35.txt | AC | 51 ms | 8484 KB |
1
|
in36.txt | AC | 55 ms | 8552 KB |
1
|
sample01.txt | AC | 23 ms | 684 KB |
1
|
sample02.txt | AC | 18 ms | 632 KB |
1
|