結果
問題 | No.1188 レベルX門松列 |
ユーザー |
![]() |
提出日時 | 2020-08-22 14:32:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 2,639 bytes |
コンパイル時間 | 2,389 ms |
コンパイル使用メモリ | 198,388 KB |
最終ジャッジ日時 | 2025-01-13 08:45:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int ll #define ll long long #define I32_MAX 2147483647 #define I64_MAX 9223372036854775807LL #define I64_MAX2 1223372036854775807LL #define INF I64_MAX2 // #define MOD 1000000007 #define MOD 998244353 #define MEM_SIZE 101010 #define DEBUG_OUT true #define ALL(x) (x).begin(), (x).end() template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";} template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;} template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } } template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);} template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}} template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T > size_t longest_increasing_subsequence(const vector< T > &a, bool strict,vector<int> &dp) { vector< T > lis; int cnt = 0; for(auto &p : a) { typename vector< T >::iterator it; if(strict) it = lower_bound(begin(lis), end(lis), p); else it = upper_bound(begin(lis), end(lis), p); if(end(lis) == it) lis.emplace_back(p); else *it = p; dp[cnt] = lis.size(); cnt++; } return lis.size(); } void solve(void) { int n;cin>>n; vector<int> vec (n,0); for (int i = 0; i < n; i++) { cin>>vec[i]; } vector<int> dp1 (n,0); vector<int> dp2 (n,0); longest_increasing_subsequence(vec,1,dp1); reverse(ALL(vec)); longest_increasing_subsequence(vec,1,dp2); reverse(ALL(dp2)); int res =0 ; for (int i = 0; i < n; i++) { int x = min(dp1[i],dp2[i]); x -=1; chmax(res,x); } reverse(ALL(vec)); for (int i = 0; i < n; i++) { vec[i] *= -1; } for (int i = 0; i < n; i++) { dp1[i] = 0; dp2[i] = 0; } longest_increasing_subsequence(vec,1,dp1); reverse(ALL(vec)); longest_increasing_subsequence(vec,1,dp2); reverse(ALL(dp2)); for (int i = 0; i < n; i++) { int x = min(dp1[i],dp2[i]); x -=1; chmax(res,x); } // DEBUG(dp1,dp2); cout<<res<<endl; return; } int32_t main(int32_t argc, const char *argv[]) { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout << std::fixed; std::cout << std::setprecision(11); solve(); return 0; }