結果
問題 | No.1188 レベルX門松列 |
ユーザー |
|
提出日時 | 2020-08-22 17:39:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 1,160 bytes |
コンパイル時間 | 1,683 ms |
コンパイル使用メモリ | 173,192 KB |
実行使用メモリ | 6,016 KB |
最終ジャッジ日時 | 2024-10-15 11:27:11 |
合計ジャッジ時間 | 3,000 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (int)(n); i ++) #define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i) using namespace std; using ll = long long; using PL = pair<ll,ll>; using P = pair<int,int>; constexpr int INF = 1000000001; constexpr long long HINF = 1000000000000000; constexpr long long MOD = 1000000007;// = 998244353; constexpr double EPS = 1e-4; constexpr double PI = 3.14159265358979; int judge(vector<ll> A,int N) { vector<ll> B(N + 1,INF); vector<int> length(N); rep(i,N) { int j = lower_bound(B.begin(),B.end(),A[i]) - B.begin(); B[j] = A[i]; length[i] = j; } reverse(A.begin(),A.end()); fill(B.begin(),B.end(),INF); int ans = 0; rep(i,N) { int j = lower_bound(B.begin(),B.end(),A[i]) - B.begin(); B[j] = A[i]; ans = max(ans,min(length[N - i - 1],j)); } return ans; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<ll> A(N); rep(i,N) cin >> A[i]; int ans = judge(A,N); rep(i,N) A[i] *= -1; ans = max(ans,judge(A,N)); cout << ans << '\n'; return 0; }