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