Submission #64339

ソースコード

?
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
165
#pragma GCC optimize "Ofast"
#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:40:01
言語 C++17
状態 Accepted
得点 1
ソースコード長 4841 Byte
最大実行時間 70 ms
最大メモリ使用量 8624 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 45 ms 4188 KB
1
in02.txt AC 24 ms 816 KB
1
in03.txt AC 53 ms 6660 KB
1
in04.txt AC 69 ms 8264 KB
1
in05.txt AC 62 ms 8336 KB
1
in06.txt AC 58 ms 8404 KB
1
in07.txt AC 70 ms 8344 KB
1
in08.txt AC 57 ms 8416 KB
1
in09.txt AC 63 ms 8356 KB
1
in10.txt AC 55 ms 8292 KB
1
in11.txt AC 55 ms 8360 KB
1
in12.txt AC 65 ms 8300 KB
1
in13.txt AC 65 ms 8236 KB
1
in14.txt AC 56 ms 8304 KB
1
in15.txt AC 63 ms 8376 KB
1
in16.txt AC 56 ms 8448 KB
1
in17.txt AC 58 ms 8388 KB
1
in18.txt AC 63 ms 8452 KB
1
in19.txt AC 60 ms 8388 KB
1
in20.txt AC 59 ms 8328 KB
1
in21.txt AC 60 ms 8392 KB
1
in22.txt AC 65 ms 8456 KB
1
in23.txt AC 62 ms 8272 KB
1
in24.txt AC 50 ms 8468 KB
1
in25.txt AC 50 ms 8408 KB
1
in26.txt AC 48 ms 8476 KB
1
in27.txt AC 27 ms 608 KB
1
in28.txt AC 15 ms 564 KB
1
in29.txt AC 22 ms 648 KB
1
in30.txt AC 21 ms 476 KB
1
in31.txt AC 17 ms 560 KB
1
in32.txt AC 17 ms 772 KB
1
in33.txt AC 15 ms 724 KB
1
in34.txt AC 24 ms 676 KB
1
in35.txt AC 60 ms 8564 KB
1
in36.txt AC 56 ms 8624 KB
1
sample01.txt AC 16 ms 756 KB
1
sample02.txt AC 16 ms 716 KB
1