結果
問題 | No.127 門松もどき |
ユーザー | imgry22 |
提出日時 | 2015-01-21 18:40:38 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,756 bytes |
コンパイル時間 | 1,344 ms |
コンパイル使用メモリ | 143,900 KB |
実行使用メモリ | 58,672 KB |
最終ジャッジ日時 | 2023-09-05 02:43:12 |
合計ジャッジ時間 | 5,288 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 267 ms
58,672 KB |
testcase_05 | WA | - |
testcase_06 | AC | 23 ms
12,916 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 3 ms
4,600 KB |
testcase_12 | AC | 132 ms
39,152 KB |
testcase_13 | AC | 169 ms
47,428 KB |
testcase_14 | AC | 170 ms
44,744 KB |
testcase_15 | AC | 228 ms
54,820 KB |
testcase_16 | AC | 147 ms
43,728 KB |
testcase_17 | AC | 171 ms
48,136 KB |
testcase_18 | AC | 145 ms
42,728 KB |
testcase_19 | AC | 88 ms
30,976 KB |
testcase_20 | AC | 89 ms
31,316 KB |
testcase_21 | AC | 43 ms
19,492 KB |
testcase_22 | AC | 284 ms
58,584 KB |
testcase_23 | AC | 254 ms
58,640 KB |
testcase_24 | AC | 213 ms
49,812 KB |
testcase_25 | AC | 242 ms
55,192 KB |
testcase_26 | AC | 118 ms
35,152 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pair<int, int> > vii; #define rrep(i, m, n) for(int (i)=(m); (i)<(n); (i)++) #define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++) #define rep(i, n) for(int (i)=0; (i)<(n); (i)++) #define rev(i, n) for(int (i)=(n)-1; (i)>=0; (i)--) #define vrep(i, c) for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++) #define ALL(v) (v).begin(), (v).end() #define mp make_pair #define pb push_back template<class T1, class T2> inline void minup(T1& m, T2 x){ if(m>x) m=static_cast<T2>(x); } template<class T1, class T2> inline void maxup(T1& m, T2 x){ if(m<x) m=static_cast<T2>(x); } #define INF 1000000000 #define MOD 1000000007 #define EPS 1E-12 const int MAX_N = 3000; int n; int A[MAX_N]; int dp[2][MAX_N][MAX_N]; int res; int lsolve(int L, int R); int rsolve(int L, int R); int lsolve(int L, int R) { if(dp[0][L][R]) return dp[0][L][R]; if(L == R) return dp[0][L][R] = 1; if(R-1 >= 0 && A[L] >= A[R]) return dp[0][L][R] = lsolve(L, R-1); return dp[0][L][R] = max(lsolve(L, R-1), rsolve(L+1, R)+1); } int rsolve(int L, int R) { if(dp[1][L][R]) return dp[1][L][R]; if(L == R) return dp[1][L][R] = 1; if(L+1 <= n-1 && A[L] <= A[R]) return dp[1][L][R] = rsolve(L+1, R); return dp[1][L][R] = max(rsolve(L+1, R), lsolve(L, R-1)+1); } int main() { cin >> n; rep(i, n) cin >> A[i]; rep(i, n) rrep(j, i+1, n) maxup(res, lsolve(i, j)); rep(i, n) rrep(j, i+1, n) maxup(res, rsolve(i, j)); /* rep(i, n) rrep(j, i+1, n){ cout << i << " " << j; maxup(res, lsolve(i, j)); cout << " o" << endl; } */ cout << res << endl; return 0; }