結果
問題 | No.127 門松もどき |
ユーザー |
![]() |
提出日時 | 2021-10-26 23:50:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,738 ms / 5,000 ms |
コード長 | 978 bytes |
コンパイル時間 | 5,790 ms |
コンパイル使用メモリ | 253,416 KB |
最終ジャッジ日時 | 2025-01-25 07:32:58 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000int get(vector<int> a){int n = a.size();vector dp(n,vector(n,vector<int>(2,-Inf)));rep(i,n){dp[i][i][0] = 1;dp[i][i][1] = 1;}for(int i=2;i<=n;i++){rep(j,n){int l = j;int r = j+i-1;if(r>=n)break;dp[l][r][0] = max(dp[l][r][0],dp[l][r-1][0]);if(a[r]>a[l])dp[l][r][0] = max(dp[l][r][0],dp[l+1][r][1]+1);dp[l][r][1] = max(dp[l][r][1],dp[l+1][r][1]);if(a[l]>a[r])dp[l][r][1] = max(dp[l][r][1],dp[l][r-1][0]+1);}}int ret = 0;rep(i,n){rep(j,n){rep(k,2){ret = max(ret,dp[i][j][k]);}}}return ret;}int main(){int n;cin>>n;vector<int> a(n);rep(i,n)cin>>a[i];int ans = get(a);rep(i,n)a[i] *= -1;// ans = max(ans,get(a));cout<<ans<<endl;return 0;}