結果
問題 |
No.127 門松もどき
|
ユーザー |
|
提出日時 | 2025-07-13 05:01:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 5,000 ms |
コード長 | 994 bytes |
コンパイル時間 | 2,098 ms |
コンパイル使用メモリ | 198,448 KB |
実行使用メモリ | 73,856 KB |
最終ジャッジ日時 | 2025-07-13 05:01:07 |
合計ジャッジ時間 | 5,522 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N); for(auto &a : A) cin >> a; vector<vector<int>> dpL(N,vector<int>(N,-1)),dpR(N,vector<int>(N,-1)); for(int i=0; i<N; i++) dpL.at(i).at(i) = 1,dpR.at(i).at(i) = 1; int answer = 0; for(int len=1; len<=N; len++) for(int l=0; ; l++){ int r = l+len-1; if(r >= N) break; answer = max({answer,dpL.at(l).at(r),dpR.at(l).at(r)}); if(l > 0){ int a = A.at(r),d = dpR.at(l).at(r); if(a > A.at(l-1)) dpL.at(l-1).at(r) = max(dpL.at(l-1).at(r),d+1); dpR.at(l-1).at(r) = max(dpR.at(l-1).at(r),d); } if(r+1 < N){ int a = A.at(l),d = dpL.at(l).at(r); if(a > A.at(r+1)) dpR.at(l).at(r+1) = max(dpR.at(l).at(r+1),d+1); dpL.at(l).at(r+1) = max(dpL.at(l).at(r+1),d); } } cout << answer << endl; }