結果
問題 | No.1368 サイクルの中に眠る門松列 |
ユーザー |
![]() |
提出日時 | 2021-01-29 21:46:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,008 bytes |
コンパイル時間 | 1,558 ms |
コンパイル使用メモリ | 172,116 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-06-27 08:00:42 |
合計ジャッジ時間 | 3,187 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; bool is_kadomatsu(const vector<ll>& v){ if(v[0] == v[1] || v[0] == v[2] || v[1] == v[2]) return false; if(v[0] < v[1] && v[1] > v[2]) return true; if(v[0] > v[1] && v[1] < v[2]) return true; return false; } void solve(){ int N; cin >> N; vector<ll> v(N); rep(i,N) cin >> v[i]; ll ret = 0; rep(i,3){ vector<ll> dp(N+10, 0); rep(j,N-2){ if(is_kadomatsu({v[j],v[j+1],v[j+2]})){ dp[j+3] = max(dp[j+3], dp[j] + v[j]); } dp[j+1] = max(dp[j+1], dp[j]); } rep(j,dp.size()) ret = max(ret, dp[j]); rotate(v.begin(), v.begin()+1, v.end()); } cout << ret << endl; } int main(){ int T; cin >> T; rep(t,T){ solve(); } return 0; }